In-place vs out-of-place algorithms

Posted in /  

In-place vs out-of-place algorithms
vinaykhatri

Vinay Khatri
Last updated on March 19, 2024

    In-Place algorithms

    This is a category of the algorithms that do not consume any extra space in order to solve a given task. They generally override the given input with the output. We can say that the auxiliary space complexity of these algorithms is O(1). These algorithms may sometimes require a very small space but that space should not depend on size of input. The algorithms that work recursively and require call stack memory are generally not considered in-place algorithms.

    Below is an example of an in-place algorithm to reverse a given array:

    #include <bits/stdc++.h>
    using namespace std;
    
    void reverseArray(int arr[], int start, int end)
    {
        while (start < end)
        {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }   
    
    int main()
    {
        int arr[] = {1, 2, 3};
    
        int n = sizeof(arr) / sizeof(arr[0]);   
    
        reverseArray(arr, 0, n-1);
    
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
    
        return 0;
    }

    Output

    3 2 1

    Out-of-Place algorithms

    These algorithms require extra memory to accomplish a given task. The time complexity of these algorithms is never constant and depends on the size of the input. Below is an algorithm to reverse a given array using extra space. The auxiliary space complexity of the algorithm is O(N).

    #include <iostream>
    using namespace std;
    int main()
    {
        int original_arr[] = {1, 2, 3};
    
        int len = sizeof(original_arr)/sizeof(original_arr[0]);
    
        int copied_arr[len], i, j;
    
        for (i = 0; i < len; i++) 
        {
            copied_arr[i] = original_arr[len - i - 1];
       }
        for(int i=0;i<len;i++) 
        {
            cout<<copied_arr[i]<<" ";
        }
        return 0;
    }

    Output

    3 2 1

    People are also reading:

    FAQs


    An in-place algorithm is one that does not consume any extra memory apart from the array used for sorting.

    An out-of-place algorithm is one that consumes extra memory depending upon the size of the input.

    Insertion sort and selection sort are two examples of in-place of algorithms.

    The best examples of out-of-place algorithms are Merge sort and counting sort.

    The fastest sorting algorithm is Quicksort.

    Leave a Comment on this Post

    0 Comments