Previous: 10.2.2 Bubble Sort
Up: 10.2 Improving Search - Sorting the Data
Previous Page: 10.2.2 Bubble Sort
Next Page: 10.3 Binary Search
Previous: 10.2.2 Bubble Sort
Up: 10.2 Improving Search - Sorting the Data
Previous Page: 10.2.2 Bubble Sort
Next Page: 10.3 Binary Search
The two sorting algorithms we have looked at so far are useful when all of the data is already present in an array, and we wish to rearrange it into sorted order. However, if we are reading the data into an array one element at a time, we can take another approach - insert each element into its sorted position in the array as we read it. In this way, we can keep the array in sorted form at all times. This algorithm is called insertion sort.
With this idea in mind, Let us see how the algorithm would work. If the array is empty, the first element read is placed at index zero, and the array of one element is sorted. For example, if the first element read is 23, then the array is:
23, ?We will use the symbol, ?, to indicate that the rest of the array elements contain garbage. Once the array is partially filled, each element is inserted in the correct sorted position. As each element is read, the array is traversed sequentially to find the correct index location where the new element should be placed. If the position is at the end of the partially filled array, the element is merely placed at the required location. Thus, if the next element read is 35, then the array becomes:
23, 35, ?However, if the correct index for the element is somewhere other than at the end, all elements with equal or greater index must be moved over by one position to a higher index. Thus, suppose the next element read is 12. The correct index for this element in the current array is zero. Each element with index zero or greater in the current partial array must be moved by one to the next higher position. To shift the elements, we must first move the last element to its (unused) higher index position, then, the one next to the last, and so on. Each time we move an element we leave a ``hole'' so we can move of the adjoining element, and so on. Thus, the sequence of moving elements for our example is:
23, 35, ?, ?
23, ?, 35, ?
?, 23, 35, ?
The index zero
is now vacant, and the new element, 12, can be put in that position.
12, 23, 35, ?
The process repeats with each element read in until the end of input. So, if the next element is 47, we would traverse from the beginning of the array until we find larger than 47 or until we reach the end of the filled part of the array. In this case, we reach the end of the array, and insert 47:
12, 23, 35, 47, ?Let us develop the algorithm in more detail by observing how we insert a new item, 30. The correct position is found by traversing the partial array as long as the new item is greater than the array element. In this case, the array traversal stops at index 2, since the element at index 2, namely 35, is grater than the new element, 30. In general, the following loop finds the correct position in an array, aray, for the new item. Notice we compare the index, i, with the variable, freepos, whose value is now 4, to know when we have reached the next free position in the array.
for (i = 0; i < freepos && item > aray[i]; i++)
;
When this loop terminates, in our case, the variable, i, will be 2.
Next, elements from index, i(2), to index freepos(4) are
moved over one position.
The highest indexed element must be moved first, then the next
highest index, and so on.
The following loop moves all elements, with index greater than or equal to i,
in a correct order:
for (k = freepos; k > i; k--)
aray[k] = aray[k - 1];
When this loop terminates, the loop counter, k, will be equal to
i, which is the index of the ``hole'' created in the array:
12, 23, ?, 35, 47Finally, the new item can be inserted at index, i. Figure 10.12 shows the complete function for inserting one new element in a sorted array, given the array, the new item, and the next free position (which, incidentally, is the current size of the array).
The function traverses the partial array until it finds either that item is less than or equal to the array element or that the array is exhausted. If the array is exhausted, the second loop is not executed since i == freepos. In this case, the item is merely inserted at the correct position. Otherwise, elements at and above index, i, are moved over one position, and the new element is inserted at the correct index.
We are now ready to implement insertion sort. The program logic is simple:
Repeat the following until end of input:
read a number,
insert the number read into the array in sorted order;
if the array is full, break out of loop.
The program terminates after a printing of the sorted array.
The program uses the
above function, insert_sorted(), to insert each number in sorted
order into the
array, and a function, pr_aray_line() of Figure 10.5,
to print the array. These
functions are included in file, sortsrch.c.
The program driver is shown in Figure 10.13.
Notice, we increment the number of elements in the array in each call
to insert_sorted(), since we have added a new element to the array.
We have included a debug statement to print out the partial array at each step. The input is terminated either when an end of file is reached or when the array becomes full.
Sample Session:
Insertion sort can be adapted to sorting an existing array. Each step works with a sub-array whose effective size increases from two to the size of the array. The element at the highest index in the sub-array is inserted into the current sub-array, the effective size is increased, etc. (see Problem 5).