Insertion Sort

This is a Java Program to implement Insertion Sort on an integer array. Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, advantages of Insertion Sort are that it is efficient for (quite) small data sets, adaptive for data sets that are already substantially sorted, stable (i.e. does not change the relative order of elements with equal keys), In-place ( i.e. only requires a constant amount O(1) of additional memory space) and online (i.e. can sort a list as it receives it).

Worst case performance : О(n2) comparisons, swaps
Best case performance : O(n) comparisons, O(1) swaps
Average case performance : О(n2) comparisons, swaps

Advantages of Insertion Sort:

1) It is very simple.
2) It is very efficient for small data sets.
3) It is stable; i.e., it does not change the relative order of elements with equal keys.
4) In-place; i.e., only requires a constant amount O(1) of additional memory space.

Insertion sort iterates through the list by consuming one input element at each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Image source: “Introduction to Algorithms”, The MIT Press

Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Another Example: 
12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

Here is the source code of the Java Program to implement Insertion Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. /*

2.  * Java Program to Implement Insertion Sort

3.  */

5. import java.util.Scanner;

7. /* Class InsertionSort */

8. public class InsertionSort 

9. {

10.     /* Insertion Sort function */

11.     public static void sort( int arr[] )

12.     {

13.         int N = arr.length;

14.         int i, j, temp;

15.         for (i = 1; i< N; i++) 

16.         {

17.             j = i;

18.             temp = arr[i];    

19.             while (j > 0 && temp < arr[j-1])

20.             {

21.                 arr[j] = arr[j-1];

22.                 j = j-1;

23.             }

24.             arr[j] = temp;            

25.         }        

26.     }    

27.     /* Main method */

28.     public static void main(String[] args) 

29.     {

30.         Scanner scan = new Scanner( System.in );        

31.         System.out.println("Insertion Sort Test\n");

32.         int n, i;

33.         /* Accept number of elements */

34.         System.out.println("Enter number of integer elements");

35.         n = scan.nextInt();

36.         /* Create integer array on n elements */

37.         int arr[] = new int[ n ];

38.         /* Accept elements */

39.         System.out.println("\nEnter "+ n +" integer elements");

40.         for (i = 0; i < n; i++)

41.             arr[i] = scan.nextInt();

42.         /* Call method sort */

43.         sort(arr);

44.         /* Print sorted Array */

45.         System.out.println("\nElements after sorting ");        

46.         for (i = 0; i < n; i++)

47.             System.out.print(arr[i]+" ");            

48.         System.out.println();                     

49.     }    

50. }

Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
999 921 823 816 767 712 698 657 532 412 391 323 287 256 225 162 123 64 24 6
 
Elements after sorting
6 24 64 123 162 225 256 287 323 391 412 532 657 698 712 767 816 823 921 999
 
 
 
Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991
 
Elements after sorting
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991
 
 
 
Insertion Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
54 135 23 75 1 576 234 928 13 84 631 1283 748 124 54 6 24 485 1024 0
 
Elements after sorting
0 1 6 13 23 24 54 54 75 84 124 135 234 485 576 631 748 928 1024 1283

ANOTHER PROGRAM ON INSERTION SORT

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class MyInsertionSort {     public static void main(String a[]){         int[] arr1 = {10,34,2,56,7,67,88,42};         int[] arr2 = doInsertionSort(arr1);         for(int i:arr2){             System.out.print(i);             System.out.print(", ");         }     }           public static int[] doInsertionSort(int[] input){                   int temp;         for (int i = 1; i < input.length; i++) {             for(int j = i ; j > 0 ; j--){                 if(input[j] < input[j-1]){                     temp = input[j];                     input[j] = input[j-1];                     input[j-1] = temp;                 }             }         }         return input;     } }

Output: 2, 7, 10, 34, 42, 56, 67, 88,

A CODE ON INSERTION SORT

// Java program for implementation of Insertion Sort class InsertionSort {     /*Function to sort array using insertion sort*/     void sort(int arr[])     {         int n = arr.length;         for (int i=1; i<n; ++i)         {             int key = arr[i];             int j = i-1;             /* Move elements of arr[0..i-1], that are                greater than key, to one position ahead                of their current position */             while (j>=0 && arr[j] > key)             {                 arr[j+1] = arr[j];                 j = j-1;             }             arr[j+1] = key;         }     }     /* A utility function to print array of size n*/     static void printArray(int arr[])     {         int n = arr.length;         for (int i=0; i<n; ++i)             System.out.print(arr[i] + " ");         System.out.println();     }     // The main method     public static void main(String args[])     {                int arr[] = {12, 14, 13, 5, 6};         InsertionSort ob = new InsertionSort();                ob.sort(arr);                   printArray(arr);     } } /* This code is contributed by Onuoha David. */

Output: 5 6 12 13 14

ANOTHER JAVA CODE ON INSERTION SORT

1. public class InsertionSortExample {  
2.     public static void insertionSort(int array[]) {  
3.         int n = array.length;  
4.         for (int j = 1; j < n; j++) {  
5.             int key = array[j];  
6.             int i = j-1;  
7.             while ( (i > -1) && ( array [i] > key ) ) {  
8.                 array [i+1] = array [i];  
9.                 i--;  
10.             }  
11.             array[i+1] = key;  
12.         }  
13.     }  
14.        
15.     public static void main(String a[]){    
16.         int[] arr1 = {9,14,3,2,43,11,58,22};    
17.         System.out.println("Before Insertion Sort");    
18.         for(int i:arr1){    
19.             System.out.print(i+" ");    
20.         }    
21.         System.out.println();    
22.             
23.         insertionSort(arr1);//sorting array using insertion sort    
24.            
25.         System.out.println("After Insertion Sort");    
26.         for(int i:arr1){    
27.             System.out.print(i+" ");    
28.         }    
29.     }    
30. }    

Output:

Before Insertion Sort
9 14 3 2 43 11 58 22 
After Insertion Sort
2 3 9 11 14 22 43 58 

THIS IS ANOTHER CODE FOR IMPLEMENTATION OF INSERTION SORT

package com.journaldev.test;

import java.util.Arrays;

public class InsertionSort {

 public static void main(String[] args) {
  int A[] = new int[10];
  populateArray(A);
  System.out.println("Before Sorting: ");
  printArray(A);
  // sort the array
  insertionSort(A);
  System.out.println("\nAfter Sorting: ");
  printArray(A);
 }

 /**
  * This method will sort the integer array using insertion sort in java algorithm
  * 
  * @param arr
  */
 private static void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
   int valueToSort = arr[i];
   int j = i;
   while (j > 0 && arr[j - 1] > valueToSort) {
    arr[j] = arr[j - 1];
    j--;
   }
   arr[j] = valueToSort;
  }
 }

 public static void printArray(int[] B) {
  System.out.println(Arrays.toString(B));
 }

 public static void populateArray(int[] B) {
  for (int i = 0; i < B.length; i++) {
   B[i] = (int) (Math.random() * 100);
  }
 }
}

I am using random number generator code and the output for me for above program is:

Before Sorting: 
[57, 90, 80, 48, 35, 91, 1, 83, 32, 53]

After Sorting: 
[1, 32, 35, 48, 53, 57, 80, 83, 90, 91]