Previous Section
 < Free Open Study > 
Next Section


3.3 Abstract Data Type Sorted List

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.

Logical Level

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 .

Application Level

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.

Implementation Level

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:

  1. Find the place where the new element belongs.

  2. Create space for the new element.

  3. 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.

Click To expand
Figure 3.4: Inserting into a sorted 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 array-based 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.

Click To expand
Figure 3.5: Retrieving in a sorted list

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 section-that is, from D to G-and so on, until we reach the single page that contains "David." Figure 3.6 illustrates this algorithm.

Click To expand
Figure 3.6: A binary search of the phone book

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 walk-through 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.

Click To expand
Figure 3.7: Trace of the binary search algorithm

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.

Table 3.1: Iteration Trace of the Binary Search Algorithm

Iteration

first

last

midPoint

info[midPoint]

Terminating Condition

item: fish

  • First

0

10

5

dog

 
  • Second

6

10

8

horse

 
  • Third

6

7

6

fish

found is true

item: snake

  • First

0

10

5

dog

 
  • Second

6

10

8

horse

 
  • Third

9

10

9

rat

 
  • Fourth

10

10

10

snake

found is true

item: zebra

  • First

0

10

5

dog

 
  • Second

6

10

8

horse

 
  • Third

9

10

9

rat

 
  • Fourth

10

10

10

snake

 
  • Fifth

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.

Table 3.2: Comparison of Linear and Binary Search
 

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

Constructor

   
  • print LengthIs

 

0

InsertItem

   
  • Insert four items and print

5, 7, 6, 9

5 6 7 9

  • Insert item and print

1

1 5 6 7 9

RetrieveItem

   
  • Retrieve 4 and print whether found

 

Item is not found

  • Retrieve 1 and print whether found

 

Item is found

  • Retrieve 9 and print whether found

 

Item is found

  • Retrieve 10 and print whether found

 

Item is not found

IsFull

   
  • Invoke (list is full)

 

List is full

  • Delete 5 and invoke

 

List is not full

DeleteItem

   
  • Delete 1 and print

 

7 6 9

  • Delete 6 and print

 

7 9

  • Delete 9 and print

 

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.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)