April 21, 2022

What is In-place Algorithm

An in-place algorithm is an algorithm that doesn’t use any extra space to transform the input. It uses the same space used by input data and modify the data with in that space itself to produce the output. However a small amount of extra storage space is allowed for auxiliary variables.

Sorting algorithms like Bubble sort, Selection Sort, Insertion Sort are in-place sorting algorithms.

Merge sort is an example of not in-place or out-of-place sorting algorithm.

Here is code snippet of bubble sort showing how the input array itself is used to produce output. With in the input array after comparing elements, swapping is done if required. Only extra space it uses is the temp variable.

int[] arr = {61, 34, 10, 0, 15, 112, 53, 78, 39, 45};
int n = arr.length;
for(int i = 0; i < n; i++){
  for(int j = 0; j < (n - i - 1); j++){
    if(arr[j] > arr[j+1]){
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp; 
    }
  }
}

Another simple example of in-place algorithm is reversing the array.

int[] arr = {61, 34, 10, 0, 15, 112, 53, 78, 39, 45};
int n = arr.length;
for (int i = 0; i < n / 2; i++) {
  int temp = arr[i];
  arr[i] = arr[n - 1 - i];
  arr[n - 1 - i] = temp;
}

That's all for the topic What is In-place Algorithm. If something is missing or you have something to share about the topic please write a comment.


You may also like

No comments:

Post a Comment