Insertion Sort In Java
- Sorts by shifting elements. All, but first element, are made as key once.
- Efficient for sorting few numbers.
- Insertion Sort is better than Selection Sort and Bubble Sort.
- Stable i.e. order of same numbers is maintained.
/* 1. All elements other than 1st are considered as key 2. The key is compared with all previous elements until key is put at right place */ //Best Case: O(n) //Worst Case: O(n^2) //Space Complexity : O(1) public class InsertionSortInJava { public static void InsertionSort(int array[]) { int n = array.length; for (int j = 1; j < n; j++) { int key = array[j]; int i = j-1; // as long as i is greater than -1 and previous element is greater than key while ( (i > -1) && ( array [i] > key ) ) { //shift the greater element to the right so that //in case we find this spot for key then we just //replace the number with key outside loop array [i+1] = array [i]; i--; } array[i+1] = key; } } public static void main( String[] args ){ int[] arr = {4,17,1,4,35,15,63,20}; System.out.println("Before Insertion Sort"); for(int i:arr){ System.out.print(i+" "); } System.out.println(); InsertionSort(arr);//sorting array using insertion sort System.out.println("After Insertion Sort"); for(int i:arr){ System.out.print(i+" "); } } } /* OUTPUT: Before Insertion Sort 4 17 1 4 35 15 63 20 After Insertion Sort 1 4 4 15 17 20 35 63 */ Insertion Sort Analysis
public class InsertionSortAnalysis { public static void InsertionSort(int array[]) { int n = array.length; System.out.println("******************"); System.out.println("ARRAY LENGTH IS: " + n); System.out.println("******************"); for (int j = 1; j < n; j++) { int key = array[j]; int i = j-1; int x = 0; for(int k:array){ if(i+1 == x) System.out.print("{ "+k+" } "); else System.out.print(k + " "); x+=1; } System.out.println(); System.out.println("---------------------"); while ( (i > -1) && ( array [i] > key ) ) { array [i+1] = array [i]; i--; } array[i+1] = key; x = 0; for(int k:array){ if(i+1 == x) System.out.print("{ "+k+" } "); else System.out.print(k + " "); x+=1; } System.out.println(); System.out.println("******************"); } } public static void main( String[] args ){ int[] arr = {4,17,1,4,35,15,63,20}; System.out.println("------------"); System.out.println("Unsorted:"); System.out.println("------------"); for(int i:arr){ System.out.print(i+" "); } System.out.println(); InsertionSort(arr); System.out.println("------------"); System.out.println("Sorted:"); System.out.println("------------"); for(int i:arr){ System.out.print(i+" "); } } } /* KEY IS DENOTED BY { } OUTPUT: ------------ Unsorted: ------------ 4 17 1 4 35 15 63 20 ****************** ARRAY LENGTH IS: 8 ****************** 4 { 17 } 1 4 35 15 63 20 --------------------- 4 { 17 } 1 4 35 15 63 20 ****************** 4 17 { 1 } 4 35 15 63 20 --------------------- { 1 } 4 17 4 35 15 63 20 ****************** 1 4 17 { 4 } 35 15 63 20 --------------------- 1 4 { 4 } 17 35 15 63 20 ****************** 1 4 4 17 { 35 } 15 63 20 --------------------- 1 4 4 17 { 35 } 15 63 20 ****************** 1 4 4 17 35 { 15 } 63 20 --------------------- 1 4 4 { 15 } 17 35 63 20 ****************** 1 4 4 15 17 35 { 63 } 20 --------------------- 1 4 4 15 17 35 { 63 } 20 ****************** 1 4 4 15 17 35 63 { 20 } --------------------- 1 4 4 15 17 { 20 } 35 63 ****************** ------------ Sorted: ------------ 1 4 4 15 17 20 35 63 */ Passes: n-1 where n denotes array length