|
|
|
|
|
|
|
Inserting into an Ordered List |
|
|
|
|
|
|
|
|
What if we want to add a new value to an already sorted list? We can store the new value at list[length], increment length, and sort the array again. However, such a solution is not an efficient way of solving the problem. Inserting five new items results in five separate sorting operations. Let's build another list operation, named Insert, that inserts a value into a sorted list. |
|
|
|
|
|
|
|
|
If we were to insert a value by hand into a sorted list, we would write the new value out to the side and draw a line showing where it belongs. We do so by scanning the list until we find a value greater than the one we are inserting. The new value goes in the list just before that point. |
|
|
|
|
|
|
|
|
We can do something similar in our function. We can find the proper place in the list using the by-hand algorithm. Instead of writing the value to the side, we have to shift all the values larger than the new one down one place to make room for it. The main algorithm is expressed as follows, where item is the value being inserted. |
|
|
|
|
|
|
|
|
WHILE place not found AND more places to look
IF item > current component in list
increment current place
ELSE
place found
Shift remainder of list down
Insert item
increment length |
|
|
|
|
|
|
|
|
Assuming that index is the place where item is to be inserted, the algorithm for Shift List Down is |
|
|
|
|
|
|
|
|
Set list[length] = list[length-1]
Set list[length-1] = list[length-2]
. .
. .
. .
Set list[index+1] = list[index] |
|
|
|
|
|
|
|
|
We can use a For loop that decrements the control variable to shift the components in the list down one position. We can code the modules Insert Item and Increment Length directly. This algorithm is illustrated in Figure 12-5. There is something familiar about the While loop in our algorithm: it is logically like the While loop in SearchOrd. In SearchOrd, we leave the loop either when we find item or when we pass the place in the list where item belongs. |
|
|
|
|
|
|
|
|
We can simply use SearchOrd to find the insertion place for us. On return from SearchOrd, if found is FALSE, index is the place in list where item should be inserted. If found is TRUE, we can either insert a second copy or |
|
|
|
|
|