[ Intro Alg ] Getting Started - Insertion sort

Preface: 
Here we will familiarize you with the framework we shall use throughout the book to think about the design and analysis of algorithms. It is self-contained, but it does include several references to material that we introduce in Chapters 3 and 4. 

We begin by examining the insertion sort algorithm to solve the sorting problem introduced in Chapter 1. We define a “pseudocode” that should be familiar to you if you have done computer programming, and we use it to show how we shall specify our algorithms. Having specified the insertion sort algorithm, we then argue that it correctly sorts, and we analyze its running time. The analysis introduces a notation that focuses on how that time increases with the number of items to be sorted. 

Insertion sort: 
Our first algorithm, insertion sort, solves the sorting problem introduced in Chapter 1: 
 

The numbers that we wish to sort are also known as the keys. Although conceptually we are sorting a sequence, the input comes to us in the form of an array with nelements. Here we shall typically describe algorithms as programs written in a pseudocode that is similar in many respects to C, C++, Java, Python, or Pascal. If you have been introduced to any of these languages, you should have little trouble reading our algorithms. What separates pseudocode from “real” code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm. Sometimes, the clearest method is English, so do not be surprised if you come across an English phrase or sentence embedded within a section of “real” code. Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering. Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely. 

We start with insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in Figure 2.1. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table. 
 

We present our pseudocode for insertion sort as a procedure called INSERTION-SORT, which takes as a parameter an array A[1..n ] containing a sequence of length nthat is to be sorted. (In the code, the number n of elements in A is denoted by A.length.) The algorithm sorts the input numbers in place: it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time. The input array A contains the sorted output sequence when the INSERTION-SORT procedure is finished. 

Loop invariants and the correctness of insertion sort: 
 

Figure 2.2 shows how this algorithm works for A=[5, 2, 4, 6, 1, 3]. The index j indicates the “current card” being inserted into the hand. At the beginning of each iteration of the for loop, which is indexed by j , the subarray consisting of elements A[1..j-1 ] constitutes the currently sorted hand, and the remaining subarray A[j+1..n] corresponds to the pile of cards still on the table. In fact, elements A[1..j-1] are the elements originally in positions 1 through j  1, but now in sorted order. We state these properties of A[1..j-1]  formally as a loop invariant. 

We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant: 
- Initialization 

It is true prior to the first iteration of the loop.

- Maintenance 

If it is true before an iteration of the loop, it remains true before the next iteration.

- Termination 

When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

When the first two properties hold, the loop invariant is true prior to every iteration of the loop. (Of course, we are free to use established facts other than the loop invariant itself to prove that the loop invariant remains true before each iteration.) Note the similarity to mathematical induction, where to prove that a property holds, you prove a base case and an inductive step. Here, showing that the invariant holds before the first iteration corresponds to the base case, and showing that the invariant holds from iteration to iteration corresponds to the inductive step. 

The third property is perhaps the most important one, since we are using the loop invariant to show correctness. Typically, we use the loop invariant along with the condition that caused the loop to terminate. The termination property differs from how we usually use mathematical induction, in which we apply the inductive step infinitely; here, we stop the “induction” when the loop terminates. 

Let us see how these properties hold for insertion sort. 
- From Initialization 

We start by showing that the loop invariant holds before the first loop iteration, when j=2. The subarray A[1.. j-1] , therefore, consists of just the single element A[1] , which is in fact the original element in A[1]. Moreover, this subarray is sorted (trivially, of course), which shows that the loop invariant holds prior to the first iteration of the loop.

- From Maintenance 

Next, we tackle the second property: showing that each iteration maintains the loop invariant. Informally, the body of the for loop works by moving A[j-1] , A[j-2] , A[j-3] (while loop) , and so on by one position to the right until it finds the proper position for A[j]  (lines 4–7), at which point it inserts the value of A[j]  (line 8). The subarray A[1..j]  then consists of the elements originally in A[1..j]  , but in sorted order. Incrementing j for the next iteration of the for loop then preserves the loop invariant.

- From Termination 

Finally, we examine what happens when the loop terminates. The condition causing the for loop to terminate is that j > A.length=n. Because each loop iteration increases j by 1, we must have j=n+1 at that time. Substituting n+1 for j in the wording of loop invariant, we have that the subarray A[1..n] consists of the elements originally in A[1..n] , but in sorted order. Observing that the subarray A[1..n] is the entire array, we conclude that the entire array is sorted. Hence, the algorithm is correct.

Implementation in C: 
Below is the implementation of Insert sort in C: 
- SortAlg.h 

view plaincopy to clipboardprint?

1. #ifndef __SORT_ALG__  
2. #define __SORT_ALG__  
3. #include   
4. using namespace std;  
5.   
6. void insertionSort(vector<int> & arr);  
7.   
8. #endif  

- SortAlg.cpp 

view plaincopy to clipboardprint?

1. #include "SortAlg.h"  
2.   
3.    
4. void swap(vector & arr, int i, int j) {    
5.     Comparable tmp = arr[i];    
6.     arr[i] = arr[j] ; arr[j] = tmp;    
7. }    
8.   
9. void insertionSort(vector<int> & arr)  
10. {  
11.     int j;  
12.     for(int i=1; i
13.     {  
14.         int key = arr[i];  
15.         j=i-1;  
16.         while(j>=0 && arr[j]>key)  
17.         {  
18.             swap(arr, j, j+1);  
19.             j--;  
20.         }  
21.     }  
22. }  

- main.cpp: 

view plaincopy to clipboardprint?

1. #include "SortAlg.h"  
2. #include   
3. using namespace std;  
4.   
5. void main()  
6. {  
7.     vector<int> ivector;  
8.     ivector.push_back(5);  
9.     ivector.push_back(2);  
10.     ivector.push_back(4);  
11.     ivector.push_back(6);  
12.     ivector.push_back(1);  
13.     ivector.push_back(3);  
14.     printf("\t[Info] Original vector: [");  
15.     for(vector<int>::iterator it = ivector.begin(); it!=ivector.end(); it++) printf("%d ", *it);  
16.     printf("]\n");  
17.     insertionSort(ivector);  
18.     printf("\t[Info] After insertSort: [");  
19.     for(vector<int>::iterator it = ivector.begin(); it!=ivector.end(); it++) printf("%d ", *it);  
20.     printf("]\n");  
21. }  

Execution output: 

[Info] Original vector: [5 2 4 6 1 3 ]
[Info] After insertSort: [1 2 3 4 5 6 ]

Supplement: 
* [ Data Structures with Java ] Section 7.1 : Insertion Sort