In-place vs out-of-place algorithms

All algorithms can be classified into in-place and out-of-place algorithms based on the amount of extra space used by them. In this quick article, we’ll explore the difference between the two.

In-place algorithms:

1. An in-place algorithm transforms the input without using any extra memory. As the algorithm executes, the input is usually overwritten by the output and no additional space is needed for this operation.

2. An in-place algorithm may require a small amount of extra memory for its operation. However, the amount of memory required must not be dependent on the input size and should be constant.

3. Several sorting algorithms rearranges the input into sorted order in-place, such as insertion sort, selection sort, quick sort, bubble sort, heap sort, etc. All these algorithms requires only constant amount of extra space for rearranging the elements in the input array itself.

4. Usually an algorithm is categorized as an in-place or a out-of-place algorithm based on the explicit storage allocated by the algorithm. However, calling a recursive algorithm as in-place is highly debatable since extra space is being used by the call stack. Although this space required by the call stack technically takes the recursive algorithms out of in-place algorithms category, the algorithms requiring only O(log(n)) additional space are considered to be in-place.

5. In-place algorithms are usually used in embedded system which runs in limited memory. They reduce the space requirements to great extent but in some cases, the algorithm time complexity increases.

Out-of-place algorithms:

1. An algorithm which is not in-place is called not-in-place or out-of-place algorithm. Unlike an in-place algorithm, the extra space used by an out-of-place algorithm depends on the input size.

2. The standard merge sort algorithm is an example of out-of-place algorithm as it requires O(n) extra space for merging. The merging can be done in-place but it increases the time complexity of the sorting routine.

Example:

Most of the algorithms can be implemented in-place as well as out-of-place. Let’s illustrate that by taking example of reversing an array of integers in Java:

1. The idea is to create a new array of same type and size, fill it with elements from original array in reverse order, and finally copy contents of the new array into the original one. Since this implementation requires O(n) extra space, this is not-in-place.

2. An in-place algorithm requires only a fixed number of integers for the auxiliary variables i, j and temp, irrespective of size of the input. This can be done by reading the elements from both ends of the array and swapping them as shown below:

This can be even done using single auxiliary variable i as shown below:

(1 votes, average: 5.00 out of 5)