Insertion Sort In Java
June 22, 2017
Categorised in: Java Codes
- 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
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.