Insertion Sort in Java and Complexity Analysis
Insertion sort consumes or marks one element in each iteration from the array of elements and grows the sorted output list.
At each iteration, insertion sort removes one element from the input array and insert that element in a location it belongs within the sorted list. And this is repeated until there are no elements remaining in the input array.
Insertion Sort Java Example
package com.sneppets.dsalgo;
public class InsertionSortExample {
public static void doInsertionSort(int[] inArray) {
int in, out, nElements;
nElements = inArray.length;
//Dividing the array of elements by marking an element
for(out=1; out<nElements; out++){
System.out.println("Marked Element: " + inArray[out]);
//Remove marked element
int temp = inArray[out];
//start shifting at out until one is smaller
System.out.println("Shifting " + inArray[out] + " until we find one number smaller");
in = out;
while(in > 0 && inArray[in - 1] >= temp)
{
System.out.println("Shift number " + inArray[in-1] +" to right and go left by one position");
//shift to right
inArray[in] = inArray[in - 1];
//go left by one position
--in;
}
//insert marked element
System.out.println("Insert "+ temp + " now");
inArray[in] = temp;
printArrayElements(inArray);
}//end for
}//end of doInsertionSort()
public static void main (String[] args){
int[] inArray = {24,10,2,30,15,6,20,8};
System.out.println("Array elements before insertion sort");
printArrayElements(inArray);
System.out.println("Performing insertion sort....");
doInsertionSort(inArray);
System.out.println("Array elements after insertion sort");
printArrayElements(inArray);
}
private static void printArrayElements(int[] inArray) {
for(int i=0; i<inArray.length; i++){
System.out.print(inArray[i] + ", ");
}
System.out.println("\n");
}
}
Output
Array elements before insertion sort 24, 10, 2, 30, 15, 6, 20, 8, Performing insertion sort.... Marked Element: 10 Shifting 10 until we find one number smaller Shift number 24 to right and go left by one position Insert 10 now 10, 24, 2, 30, 15, 6, 20, 8, Marked Element: 2 Shifting 2 until we find one number smaller Shift number 24 to right and go left by one position Shift number 10 to right and go left by one position Insert 2 now 2, 10, 24, 30, 15, 6, 20, 8, Marked Element: 30 Shifting 30 until we find one number smaller Insert 30 now 2, 10, 24, 30, 15, 6, 20, 8, Marked Element: 15 Shifting 15 until we find one number smaller Shift number 30 to right and go left by one position Shift number 24 to right and go left by one position Insert 15 now 2, 10, 15, 24, 30, 6, 20, 8, Marked Element: 6 Shifting 6 until we find one number smaller Shift number 30 to right and go left by one position Shift number 24 to right and go left by one position Shift number 15 to right and go left by one position Shift number 10 to right and go left by one position Insert 6 now 2, 6, 10, 15, 24, 30, 20, 8, Marked Element: 20 Shifting 20 until we find one number smaller Shift number 30 to right and go left by one position Shift number 24 to right and go left by one position Insert 20 now 2, 6, 10, 15, 20, 24, 30, 8, Marked Element: 8 Shifting 8 until we find one number smaller Shift number 30 to right and go left by one position Shift number 24 to right and go left by one position Shift number 20 to right and go left by one position Shift number 15 to right and go left by one position Shift number 10 to right and go left by one position Insert 8 now 2, 6, 8, 10, 15, 20, 24, 30, Array elements after insertion sort 2, 6, 8, 10, 15, 20, 24, 30,
At the end of each iteration, following the insertion of marked element in the sorted list, the elements with smaller indices are partially sorted.
It is twice as fast as bubble sort and somewhat faster than the selection sort in normal situations. It is often used with quicksort in final stages of more sophisticated sorts to achieve better performance.
Time Complexity
Let’s check how many number of comparisons and copies required by this algorithm.
In the first iteration, it compares maximum of one element in the array. In the second iteration, it compares maximum of two elements in the array, and so on, up to maximum of (n-1) comparisons.
1 + 2 + 3 + ... (n-1) = n*(n-1)/2
If in each iteration an average of only half of the elements in the array are actually compared before finding the insertion point, then we can divide by 2 which gives
n*(n-1)/4
We can say approximately the number of copies is same as number of comparisons. Though, the copy operation here is not time consuming as compared to swap operation.
For some random data this algorithm runs twice as fast as bubble sort and faster than selection sort. So we can say insertion sort runs in O(n2) time for random data.
And for the input array which is already sorted or almost sorted it does much better, because the condition in the while loop will be never true, so it’s just a simple statement in the outer for loop which executes (n-1) times. So we can say the algorithms takes O(n) time to run in this case.
Space Complexity
Since you are sorting in place you don’t need any additional space for the data. Hence the space complexity of insertion sort is O(1).
Recommended Posts
- Selection Sort and Complexity Analysis
- Bubble Sort and Complexity Analysis
- Running time in Big O notation for Java Arrays Algorithms