An Introduction to Sorting - Data Structures and Abstractions with Java - page 200

FIGURE 8-5

An insertion sort of books

Sorted

1. Remove the next unsorted book.
2. Slide the sorted books to the right one by one until
you find the right spot for the removed book.
3. Insert the topic into its new position.

Iterative Insertion Sort
8.11

An insertion sort of an array partitions —that is, divides—the array into two parts. One part is
sorted and initially contains just the first entry in the array. The second part contains the remaining
entries. The algorithm removes the first entry from the unsorted part and inserts it into its proper
sorted position within the sorted part. Just as you did with the bookshelf, you choose the proper
position by comparing the unsorted entry with the sorted entries, beginning at the end of the sorted
part and continuing toward its beginning. As you compare, you shift array entries in the sorted part
to make room for the insertion.
Figure 8-6 illustrates these steps for a sort that has already positioned the first three entries of
the array. The 3 is the next entry that must be placed into its proper position within the sorted
region. Since 3 is less than 8 and 5 but greater than 2, the 8 and 5 are shifted to make room for the 3.
Figure 8-7 illustrates an entire insertion sort of an array of integers. At each pass of the algo-
rithm, the sorted part expands by one e ntry as the unsorted part shrinks by one entry. Eventually,
the unsorted part is empty and the array is sorted.
The following iterative algorithm describes an insertion sort of the entries at indices first
through last of the array a . To sort the first n entries in the array, the call to the algorithm would be
insertionSort(a, 0, n - 1) .

Algorithm insertionSort(a, first, last)
// Sorts the array entries a[first] through a[last] iteratively.

for (unsorted = first + 1 through last)
{

nextToInsert = a[unsorted]
insertInOrder(nextToInsert, a, first, unsorted - 1)

}

The sorted part contains one entry, a[first] , and so the loop in the algorithm begins at index
first + 1 and processes the unsorted part. It then invokes another method— insertInOrder —to
perform the insertions. In the pseudocode that follows for this method, anEntry is the value to be
inserted into its proper position, and begin and end are array indices.
Algorithm insertInOrder(anEntry, a, begin, end)
// Inserts anEntry into the sorted entries a[begin] through a[end] .
index = end // index of last entry in the sorted portion
// make room, if needed, in sorted portion for another entry