Insertion Sort
Insertion sort: Insertion sort, solves the sorting problem
- Input:A sequence of n numbers 〈a1, a2, . . .,an〉.
- Output:A permutation (reordering) (a’1, a’2, . . .,a’n) of the input sequence such that (a’1 ≤ a’2 ≤ . . .≤ a’n).
The numbers that we wish to sort are also known as the keys.
Insertion sortis 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.
Our pseudo-code for insertion sort is presented as a procedure called INSERTION-SORT, which takes as a parameter an array A[1 ‥n] containing a sequence of length n that is to be sorted. (In the code, the number n of elements in A is denoted by length [A].) The input numbers are sorted in place: the numbers are rearranged 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 INSERTION-SORT is finished.
INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 ▹Insert A[j] into the sorted sequence A[1 ‥j - 1].
4 i ← j - 1
5 while i > 0 and A[i] > key
6 do A[i 1] ← A[i]
7 i ← i - 1
8 A[i 1] ← key
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 "outer" for loop, which is indexed by j, the sub array consisting of elements A[1 ‥j - 1] constitute the currently sorted hand, and elements A[j 1 ‥n] correspond 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:
At the start of each iteration of the for loop of lines 1-8, the subarray A[1 ‥j - 1] consists of the elements originally in A[1 ‥j - 1] but in sorted order.
Figure 2.2: The operation of INSERTION-SORT on the array A = 〈5, 2, 4, 6, 1, 3〉. Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles. (a)-(e) The iterations of the for loop of lines 1-8. In each iteration, the black rectangle holds the key taken from A[j], which is compared with the values in shaded rectangles to its left in the test of line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows indicate where the key is moved to in line 8. (f) The final sorted array.
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. 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 is like the base case, and showing that the invariant holds from iteration to iteration is like the inductive step.
The third property is perhaps the most important one, since we are using the loop invariant to show correctness. It also differs from the usual use of mathematical induction, in which the inductive step is used infinitely; here, we stop the "induction" when the loop terminates.