[ Data Structures with Java ] Section 7.1 : Insertion Sort

Preface : 
Teachers often have the chore of putting exams in alphabetical order before returning them to students. By looking in on the process, we discover the insertion algorithm. Initially, the papers are in random order. Assuming that the first name is correctly positioned, the sort begins with the name on the second paper. If that paper is out of order, it is moved forward to the front of the pile. The third name might be in order (name3 > name2). If not, it is moved forward in front of the second paper and compared. If it is still out of order, it is forward in front of the first paper. Repeat the process for the forth, fifth and subsequent names. By successive comparison of the name on the new paper with each preceding paper, we find the place to insert the new paper. Let us look at the insertion sort algorithm for the list of file names : Monre, Chin, Flores, Stein and Dare : 
 

The method insertionSort() takes an array arr as an argument and implements the insertion sort algorithm. Assume that n is the length of the array. The ordering assumes that the first element is in its correct position, so the method requires n-1 passes in the range from 1 to n-1 to order the remaining elements. The following is a generic version of insertionSort(). The method assumes arr is a generic array of elements whose type implements theComparable interface : 

- 函式 insertionSort() 範例代碼 :

view plaincopy to clipboardprint?

1. public static extends Comparablesuper T>> void insertionSort(T[] arr) {  
2.     int j,n = arr.length;  
3.     T target;  
4.     for(int i=1; i
5.         target = arr[i];  
6.         j=i;  
7.         while(j>0 && arr[j-1].compareTo(target)>0) {  
8.             arr[j] = arr[j-1];  
9.             arr[j-1] = target;                
10.             j--;  
11.         }  
12.         if(i!=j){arr[j]=target;}  
13.     }  
14. }  

Below is the sample code to test the method insertionSort() : 

- Sample code to test insertionSort() :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     Random rnd = new Random();  
3.     Integer[] arr = new Integer[15];  
4.     for(int i=0; i<15; i++) {  
5.         arr[i] = rnd.nextInt(100);  
6.     }  
7.     System.out.println("Array(before): "+Arrays.toString(arr));  
8.     Arrays.insertionSort(arr);  
9.     System.out.println("Array(After): "+Arrays.toString(arr));  
10. }  

Output : (one possible) 

Array(before): [19, 19, 76, 39, 58, 45, 77, 59, 22, 51, 58, 69, 83, 44, 64, 25]
Array(After): [19, 19, 22, 25, 39, 44, 45, 51, 58, 58, 59, 64, 69, 76, 77, 83]

Insertion Sort Efficiency : 
Assuming that n is the length of the array, the insertion sort requires n-1 passes. For a general pass i, the insertion occurs in the sublist arr[0] to arr[i-1] and requires on the average i/2 comparisons. The average total number of comparisons is : 
T(n) = 1/2 + 2/2 + 3/2 + ... + (n-2)/2 + (n-2)/2 = n(n-1)/4 

From the dominant term in T(n), the average-case running time of the algorithm is O(n2^2), which measures the number of comparisons. The best case occurs when the original list is already sorted. In step i, the insertion occurs at arr[i] after only one comparison. The total number of comparisons is n-1, with running time O(n). The worst case has the running time O(n^2). 
In general, the insertion sort exhibits the best performance among the quadratic sorting algorithms. The quadratic algorithms are efficient for a list having a small number of elements, say n<= 15. Recall that the insertion sort is linear (O(n)) when the list is already sorted. The insertion sort is still linear when the list is "almost sorted". This condition occurs when many of its elements are already in their correct places. Some more advanced sorting algorithms exploit this fact by partially ordering an array with an O(nlog2(n)) sorting algorithm such as quicksort.