Insertion
sort is an efficient algorithm for sorting a small
number of elements. Insertion sort works the same way as one would sort
a
bridge or gin rummy hand, i.e. starting with an empty left hand and the
cards face down on the table. One card at a time is then removed from
the table and inserted into the correct position in the left hand. To
find the correct position for a card, it is compared with each of the
cards already in the hand, from right to left. The pseudocode for
insertion sort is presented in 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. The input array A
contains the sorted output sequence when INSERTION-SORT is finished.
INSERTION-SORT (A)
1 forj <- 2 tolength[A]
2 dokey <- A[j]
3 Insert A[j] into the sorted sequence A[1 . . j - 1].
4 i <- j - 1
5 whilei > 0 and A[i]> key
6 do A[i + 1] <- A[i]
7 i <- i - 1
8 A[i + 1] <- key
Figure 1.1 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. Array
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. The index j moves left
to right through the array. At each iteration of the "outer" for loop,
the element A[j] is picked out of the array (line 2).
Then, starting in position j - 1, elements are successively
moved one position to the right until the proper position for A[j]
is found (lines 4-7), at which point it is inserted (line 8).
Figure 1.1 The operation of INSERTION-SORT on the array A = {5, 2, 4, 6, 1, 3}. The
position of index j is indicated by a circle.
In order to analyze
insertion sort the INSERTION-SORT procedure is presented with
the time "cost" ofeach statement and the
number of times each statement is executed. For each j = 2, 3, . . . ,
n, where n =length[A], tj is the
number of times the while loop test in line 5 is executed for that
value of j. It is assumed that comments are not executable statements,
and as such they take no time. The running time of the algorithm is the
sum of
running times for each statement executed; a statement that takes ci
steps to execute and is executed n times will contribute ci n to the
total running time 3. To compute T(n), the running time of
INSERTION-SORT, the products of the cost and times columns are summed.
The insertion sort
algorithm involves:
Start with the result
as the first element of the input.
Loop over the input until
it is empty, "removing" the first remaining (leftmost) element.
Compare the removed
element against the current result, starting from the highest
(rightmost) element, and working left towards the lowest element.
If the removed input
element is lower than the current result element, copy that value into
the following element to make room for the new element below, and
repeat with the next lowest result element.
Otherwise,
the new element is in the correct location; save it in the cell left by
copying the last examined result up, and start again from (2) with the
next input element.