Insertion sort is a simple sorting algorithm suited for small data sets. During each iteration, the algorithm
- Removes an element from an array
- Compares it against the largest value in the array
- Moves the element to its correct location.
Here is how the process works graphically
JAVA program to sort an array using Insertion sort algorithm.
package com.guru99;
public class InsertionSortExample {
public static void main(String a[])
{
int[] myArray = {860,8,200,9};
System.out.println("Before Insertion Sort");
printArray(myArray);
insertionSort(myArray);//sorting array using insertion sort
System.out.println("After Insertion Sort");
printArray(myArray);
}
public static void insertionSort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; i++)
{ System.out.println("Sort Pass Number "+(i));
int key = arr[i];
int j = i-1;
while ( (j > -1) && ( arr [j] > key ) )
{
System.out.println("Comparing "+ key + " and " + arr [j]);
arr [j+1] = arr [j];
j--;
}
arr[j+1] = key;
System.out.println("Swapping Elements: New Array After Swap");
printArray(arr);
}
}
static void printArray(int[] array){
for(int i=0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
}
}
Output:
Before Insertion Sort 860 8 200 9 Sort Pass Number 1 Comparing 8 and 860 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 200 860 9 Sort Pass Number 3 Comparing 9 and 860 Comparing 9 and 200 Swapping Elements: New Array After Swap 8 9 200 860 After Insertion Sort 8 9 200 860
