An in-place algorithm is an algorithm that doesn’t use any auxiliary space to transform the input. Though theoretically that would mean if you have an array of length n then you should use that n space itself to transform the input array but in reality you will definitely use some variables and index for array and that kind of auxiliary space is allowed for an in-place algorithm.
Examples of in-place algorithm are sorting algorithms like Bubble sort, Selection Sort, Insertion Sort which doesn’t require any extra space to perform sorting. That is why space complexity for these algorithms is O(1).
Merge sort, Bucket sort are examples of not in-place or out-of-place sorting algorithms.
In-place algorithm example
Let’s try to understand this auxiliary space requirement of in-place algorithm by taking an algorithm to reverse an array by using separate input and output arrays making it a not in-place algorithm.
import java.util.Arrays;
public class ReverseArray {
public static void main(String[] args) {
int[] intArr = {47, 85, 47, 34, 7, 10, 0, 106, 2, 54};
reverseArray(intArr);
}
static void reverseArray(int[] intArray) {
int n = intArray.length;
// Using another array
int[] tempArray = new int[n];
for (int i = 0; i < n; i++) {
tempArray[n - i - 1] = intArray[i];
}
System.out.println("Reversed Array- " + Arrays.toString(tempArray));
}
}
But the algorithm to reverse an array can very well be written to use the same input array to reverse it. There is no need to use a separate array making it an in-place algorithm.
public class ReverseArray {
public static void main(String[] args) {
int[] intArr = {47, 85, 47, 34, 7, 10, 0, 106, 2, 54};
reverseArray(intArr);
}
static void reverseArray(int[] intArray) {
int n = intArray.length;
for (int i = 0; i < n / 2; i++) {
int temp = intArray[i];
intArray[i] = intArray[n - 1 - i];
intArray[n - 1 - i] = temp;
}
System.out.println("Reversed Array- " + Arrays.toString(intArray));
}
}
That's all for this topic What is In-place Algorithm. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-