< Free Open Study > 
At the beginning of this chapter, we said that a list is a linear sequence of items; from any item (except the last) you can access the next item. We looked at the specifications and implementation for the operations that manipulate a list and guarantee this property.
Now we want to add another property: the key member of any item (except the first) comes before the key member of the next one. We call a list with this property a sorted list.
When we defined the specification for the Unsorted List ADT, we commented that nothing in the specification prevented the list from being stored and maintained in sorted order. Now, we must change the specification to guarantee that the list is sorted. We must add preconditions to those operations for which order is relevant. The observer functions do not change the state of the list, so we do not have to change them. Likewise, the algorithm for , can be improved but works on a sorted list. The algorithms for and are not changed by the additional property. What, then, must be changed? and .
The application level for the Sorted List ADT is the same as that for the Unsorted List ADT. As far as the user is concerned, the interfaces are the same. The only difference is that when GetNextItem is called in the Sorted List ADT, the element returned is the next one in order by key. If the user wants that property, the client code includes the file containing the class SortedType rather than UnsortedType.
InsertItem Operation To add an element to a sorted list, we must first find the place where the new element belongs, which depends on the value of its key. Let's use an example to illustrate the insertion operation. Suppose that Becca has made the honor roll. To add the element Becca to the sorted list pictured in Figure 3.4(a) while maintaining the alphabetic ordering, we must accomplish three tasks:
Find the place where the new element belongs.
Create space for the new element.
Put the new element in the list.
The first task involves traversing the list and comparing the new item to each item in the list until we find an item where the new item is less (in this case, Becca). We set moreToSearch to false when we reach a point where item.ComparedTo(Info(location)) is LESS. At this point, location indicates where the new item should go (see Figure 3.4b). If we don't find a place where item.ComparedTo (Info(location)) is LESS, then the item should be put at the end of the list. In this case, location equals length.
Now that we know where the element belongs, we need to create space for it. Because the list is sorted, Becca must be put into the list at Info(location). Of course, this position may already be occupied. To "create space for the new element," we must move down all list elements that follow it, from location through length  1. Then, we just assign item to Info(location) and increment length. Figure 3.4(c) shows the resulting list.
Let's summarize these observations in algorithm form before we write the code:
Recall that the preconditions on InsertItem state that the item is not already present in the list, so we do not need to have EQUAL as a label in the switch statement. Translating the list notation into the arraybased implementation gives us the following function:
void SortedType::InsertItem(ItemType item) { bool moreToSearch; int location = 0; moreToSearch = (location < length); while (moreToSearch) { switch (item.ComparedTo(info[location])) { case LESS : moreToSearch = false; break; case GREATER : location++; moreToSearch = (location < length); break; } } for (int index = length; index > location; index) info[index] = info[index  1]; info[location] = item; length++; }
Does this function work if the new element belongs at the beginning or the end of the list? Draw a picture to confirm for yourself how the function works in each case.
DeleteItem Operation When discussing the function DeleteItem for the Unsorted List ADT, we commented that if the list was sorted, we would have to move the elements up one position to cover the one being removed. Moving the elements up one position is the mirror image of moving the elements down one position. The loop control for finding the item to delete is the same as for the unsorted version.
Examine this algorithm carefully and convince yourself that it is correct. Try cases where you are deleting the first item and the last one.
void SortedType::DeleteItem(ItemType item) { int location = 0; while (item.ComparedTo(info[location]) != EQUAL) location++; for (int index = location + 1; index < length; index++) info[index  1] = info[index]; length; }
Improving the RetrieveItem Operation If the list is not sorted, the only way to search for a value is to start at the beginning and look at each item in the list, comparing the key member of the item for which we are searching to the key member of each item in the list in turn. We used this algorithm in the RetrieveItem operation in the Unsorted List ADT.
If the list is sorted by key value, there are two ways to improve the searching algorithm. The first way is to stop when we pass the place where the item would be found if it were present. Look at Figure 3.5(a). If you are searching for Chris, a comparison with Judy would show that Chris is LESS. Thus you have passed the place where Chris would be found if it were present. At this point you can stop and return found as false. Figure 3.5(b) shows what happens when you are searching for Susy: location is equal to 4, moreToSearch is false, and found is false.
If the item we are seeking appears in the list, the search is the same for both the unsorted list and the sorted list. When the item is not there, however, the new algorithm is better. We do not have to search all of the items to confirm that the one we want is not present. When the list is sorted, however, we can improve the algorithm even more.
Binary Search Algorithm Think of how you might go about finding a name in a phone book, and you can get an idea of a faster way to search. Let's look for the name "David." We open the phone book to the middle and see that the names there begin with M. M is larger than D, so we search the first half of the phone book, the section that contains A to M. We turn to the middle of the first half and see that the names there begin with G. G is larger than D, so we search the first half of this section, from A to G. We turn to the middle page of this section, and find that the names there begin with C. C is smaller than D, so we search the second half of this sectionthat is, from D to Gand so on, until we reach the single page that contains "David." Figure 3.6 illustrates this algorithm.
We begin our search with the whole list to examine; that is, our current search area goes from info [0] through info [length  1]. In each iteration, we split the current search area in half at the midpoint; if the item is not found there, we search the appropriate half. The part of the list being searched at any time is the current search area. For instance, in the first iteration of the loop, if a comparison shows that the item comes before the element at the midpoint, the new current search area goes from index 0 through the midpoint  1. If the item comes after the element at the midpoint, the new current search area goes from the midpoint + 1 through index length  1. Either way, the current search area has been split in half. We can keep track of the boundaries of the current search area with a pair of indexes, first and last. In each iteration of the loop, if an element with the same key as item is not found, one of these indexes is reset to shrink the size of the current search area.
How do we know when to quit searching? Two terminating conditions are possible: item is not in the list and item has been found. The first terminating condition occurs when there's no more to search in the current search area. The second terminating condition occurs when item has been found.
Notice that when we look in the lower half or upper half of the search area, we can ignore the midpoint because we know it is not there. Therefore, last is set to midPoint  1, or first is set to midPoint + 1. The coded version of our algorithm follows:
void SortedType::RetrieveItem(ItemType& item, bool& found) { int midPoint; int first = 0; int last = length  1; bool moreToSearch = first <= last; found = false; while (moreToSearch && !found) { midPoint = (first + last) / 2; switch (item.ComparedTo(info[midPoint])) { case LESS : last = midPoint  1; moreToSearch = first <= last; break; case GREATER : first = midPoint + 1; moreToSearch = first <= last; break; case EQUAL : found = true; item = info[midPoint]; break; } } }
Let's do a walkthrough of the binary search algorithm. We are searching for the item "bat." Figure 3.7(a) shows the values of first, last, and midPoint during the first iteration. In this iteration, "bat" is compared with "dog," the value in info [midpoint]. Because "bat" is less than (comes before) "dog," last becomes midPoint  1 and first stays the same. Figure 3.7(b) shows the situation during the second iteration. This time, "bat" is compared with "chicken," the value in info [midpoint]. Because "bat" is less than (comes before) "chicken," last becomes midPoint  1 and first again stays the same.
In the third iteration (Figure 3.7c), midPoint and first are both 0. The item "bat" is compared with "ant," the item in info [midpoint]. Because "bat" is greater than (comes after) "ant," first becomes midPoint + 1. In the fourth iteration (Figure 3.7d), first, last, and midPoint are all the same. Again, "bat" is compared with the item in info [middle]. Because "bat" is less than "cat," last becomes midpoint  1. Now that last is less than first, the process stops; found is false.
The binary search is the most complex algorithm that we have examined so far. Table 3.1 shows first, last, midpoint, and info [midpoint] for searches of the items "fish," "snake," and "zebra," using the same data as in the previous example. Examine the results in Table 3.1 carefully.
Iteration 
first 
last 
midPoint 
info[midPoint] 
Terminating Condition 

item: fish 


0 
10 
5 
dog 


6 
10 
8 
horse 


6 
7 
6 
fish 
found is true 
item: snake 


0 
10 
5 
dog 


6 
10 
8 
horse 


9 
10 
9 
rat 


10 
10 
10 
snake 
found is true 
item: zebra 


0 
10 
5 
dog 


6 
10 
8 
horse 


9 
10 
9 
rat 


10 
10 
10 
snake 


11 
10 
last < first 
Notice that the loop never executes more than four times. It never executes more than four times in a list of 11 components because the list is cut in half each time through the loop. Table 3.2 compares a linear search and a binary search in terms of the average number of iterations needed to find an item.
Average Number of Iterations 


Length 
Linear Search 
Binary Search 
10 
5.5 
2.9 
100 
50.5 
5.8 
1,000 
500.5 
9.0 
10,000 
5000.5 
12.4 
If the binary search is so much faster, why not use it all the time? It is certainly faster in terms of the number of times through the loop, but more computations are executed within the binary search loop than in the other search algorithms. If the number of components in the list is small (say, less than 20), the linear search algorithms are faster because they perform less work at each iteration. As the number of components in the list increases, however, the binary search algorithm becomes relatively more efficient. Always remember that the binary search requires the list to be sorted and sorting takes time.
Test Plan We can use the same test plan that we employed with the unsorted list with the expected outputs changed to reflect the ordering. We need to modify the items to be deleted to reflect where the items fall in the list; that is, we need to delete one from each end as well as from in the middle.
Operation to Be Tested and Description of Action 
Input Values 
Expected Output 


0 

InsertItem 


5, 7, 6, 9 
5 6 7 9 

1 
1 5 6 7 9 
RetrieveItem 


Item is not found 


Item is found 


Item is found 


Item is not found 

IsFull 


List is full 


List is not full 

DeleteItem 


7 6 9 


7 9 


7 
On the Web, the file SlistType.in contains the input to listDr.cpp (the test driver) that reflects this test plan; SlistType.out and SlistTest.screen contain the output.
< Free Open Study > 
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) 