|
|
|
|
|
|
|
{
Boolean placeFound; // True if item is already in the list
int index; // Position where item belongs
int count; // Loop control variable
SearchOrd(list, item, length, index, placeFound);
// Shift list[index..length-1] down one
for (count = length - 1; count >= index; count--)
// Invariant (prior to test):
// list[length-1..count+1] have been shifted down
// && length - 1 >= count >= index - 1
list[count+1] = list[count];
// Insert item
list[index] = item;
// Increment length of list
length++;
}
//******************************************************************
void SearchOrd(
/* inout */ ItemType list[], // List to be searched
/* in */ ItemType item, // Item to be found
/* in */ int length, // Length of list
/* out */ int& index, // Location of item if found
/* out */ Boolean& found ) // True if item is found
{
.
. // Same as before
.
} |
|
|
|
|
|
|
|
|
Notice that the Insert function works even if the list is empty. SearchOrd stores item into list[0], where it is immediately found. On return from SearchOrd, index is O. Because index is greater than the value of length-1 (which is -1), the body of the For loop is not executed. item is then stored into the first position in list, and length is set to 1. This algorithm also works if item is larger than any component in the list. When this happens, index equals length, and item is placed at the end of the list. |
|
|
|
|
|
|
|
|
This algorithm is the basis for another sorting algorithm-an insertion sort. In an insertion sort, values are inserted one at a time into a list that was originally empty. An insertion sort is often used when input data must be |
|
|
|
|
|