Thursday, July 23, 2020

What is In-place Algorithm

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 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

  1. Shell Sort Program in Java
  2. Tree Sort in Java Using Binary Search Tree
  3. Linear Search (Sequential Search) Java Program
  4. Reverse Each Word of The String - Java Program
  5. How to Remove Elements From an Array - Java Program

You may also like-

  1. Converting String to Enum Type - Java Program
  2. How to Read File From The Last Line in Java
  3. Java Program to Get Current Date and Time
  4. Running Dos/Windows Commands From Java Program
  5. How to Loop Through a Map in Java
  6. Difference Between Abstract Class And Interface in Java
  7. Angular One-Way Data Binding Using String Interpolation
  8. Changing String Case in Python