Java Insertion Sort

The Insertion Sort algorithm is used to specify all the data present in an array and it wish to rearrange it order and the sort them at highest index position. However, if the data are reading into the array, the one element has to be replaced at the time and insert the element for sorting position in the array. In this way, it can keep the array in sorted form at all times and often called as insertion sort. If the array is empty, it needs to insert the array into the elements and it is allowed to sort one element.

For example, if the array is to read 23 then, you can make the symbol to specify the partially filled elements in the array. Hence, the element is merely placed at the required location and the next element is placed at 35. The entire elements with equal or greater index must be moved over by one position at a higher index. Then, you can fix any array to enter in the element for higher index. If the element is moved to the higher index position, then the element can be pushed and insert the new array in the element list.

The simple insertion sort may be considered as a general selection sort in which the priority queue is implemented as an ordered array. The simple insertion sort is effective if it is small in size. This method uses very small memory and hence it is effective.

Algorithm:

[java]

for (int i = 0; i < n; i++)
temp = a[i];
for (int j = i-1; j >=0 && temp < a[j]; j–)
a[j+1]=a[j]

swap(a[i],a[j+1]);
end for
end for

[/java]

Example:

import java.util.Scanner;

/** * * @author chandrashekhar */
public class InsertionSortDemo {
  int a[];
  int n;

  public InsertionSortDemo(int size) {
    n = size;
    a = new int[n];
  }

  public void readArray() {
    Scanner s = new Scanner(System.in);
    System.out.println("Enter " + n + " Elements");
    for (int i = 0; i < n; i++) {
      a[i] = s.nextInt();
    }
  }

  public void showArray() {
    System.out.println("");
    for (int i = 0; i < n; i++) {
      System.out.print(a[i] + " ");
    }
    System.out.println("");
  }

  public void insertionSort() {
    int i, j;
    for (i = 1; i < n; i++) {
      int temp = a[i];
      for (j = i - 1; j >= 0 && temp < a[j]; j--) {
        a[j + 1] = a[j];
      }
      a[j + 1] = temp;
      System.out.println("After " + i + " Phase");
      showArray();
    }
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    System.out.println("Enter Array Size");
    int n = s.nextInt();
    InsertionSortDemo demo = new InsertionSortDemo(n);
    demo.readArray();
    System.out.println("Before InsertionSort");
    demo.showArray();
    demo.insertionSort();
    System.out.println("After InsertionSort");
    demo.showArray();
  }
}

Output :

Enter Array Size : 8 
Enter 8 Elements : 25 57 48 37 12 92 86 33 
Before Insertion Sort : 25 57 48 37 12 92 86 33 
After 1 Phase : 25 57 48 37 12 92 86 33 
After 2 Phase : 25 48 57 37 12 92 86 33 
After 3 Phase : 25 37 48 57 12 92 86 33 
After 4 Phase : 12 25 37 48 57 92 86 33 
After 5 Phase : 12 25 37 48 57 92 86 33 
After 6 Phase : 12 25 37 48 57 86 92 33 
After 7 Phase : 12 25 33 37 48 57 86 92 
After Insertion Sort : 12 25 33 37 48 57 86 92

Happy Learning 🙂