The next sort to be considered is insertion sort. An insertion sort works by assuming that all entries in the array are already in sorted order and inserting the next entry in its proper place in the order. Figure 8.5 presents an example of an insertion sort.
In this example the same array, data, is used as for the bubble sort. Each record is processed in turn, starting from the second. Figure 8.5(a) represents the situation after processing of the first six records. The seventh is yet to be processed. It is processed, as are all the other records, by assuming the preceding records are already in sorted order. Notice that records 1? are in order. To insert the seventh record, 75, into its proper place among the first seven records, compare record 7 with its predecessor, record 6. Since 75 exceeds 10, it should go somewhere higher up in the array, so compare it to the predecessor of record 6, record 5. Since 75 exceeds 32, compare it to the predecessor of record 5, record 4.
Again, 75 exceeds that element's value of 32, so compare it to its predecessor's value, 65. The last comparison is with 78. Since 75 does not exceed 78, record 7 must be inserted between record 2, where 78 is now, and record 3. To do this, move records 3 to 6 down one element, respectively, and place 75 in record 3. The result is Figure 8.5(b).
K has been updated by 1, so it points to the next record to be inserted. This algorithm for an insertion sort can be described by a loop structure in which k varies from 2 to n, as in the following function.
#define TRUE 1
#define FALSE 0
#define MAX 100
typedef struct
{
int key;
}record;
typedef record recordarray [MAX];
insertionsort (data, n)
/* Sorts the n records stored in array data
in descending order.
*/
recordarray data;
int n;
{
int k, i, inserted;
for (k=2;k<=n; k++)
{
i = k;
inserted = FALSE;
while ((i > 1) && !inserted)
if (data[i - l].key < data[i].key)
{
interchange(data,i,i - 1);
i--;
}
else
inserted = TRUE;
}
}
Within the loop, process the kth record by inserting it properly among the top k elements. This may be accomplished by another loop, in which record k is compared to each consecutive predecessor until it does not exceed the current predecessor record. It is inserted at that point in the array. As an exercise, you should modify the insertionsort program to incorporate the programming trick of Section 8.2.2. In Table 8.1 (see Section 8.7), this is referred to as the modified insertion sort.