Previous Section
 < Free Open Study > 
Next Section


Case Study

Quick Sort

In Chapter 3, we presented two versions of the List ADT: one unsorted and one created and maintained in sorted order by a unique key. In Chapter 10, we look at a variety of sorting algorithms. At the logical level, sorting algorithms take an unsorted list object and convert it into a sorted list object. At the implementation level, they take an array and reorganize the values in the array to order them by key.

The quick sort algorithm is based on the idea that it is faster and easier to sort two small lists than one large list. Its name comes from the fact that, in general, quick sort can sort a list of data elements quite rapidly. The basic strategy of this sort is to "divide and conquer."

If you were given a large stack of final exams to sort by name, you might use the following approach: Pick a splitting value, say L, and divide the stack of tests into two piles, A-L and M-Z. (Note that the two piles do not necessarily contain the same number of tests.) Then take the first pile and subdivide it into two piles, A-F and G-L. The A-F pile can be further broken down into A-C and D-F. This division process goes on until the piles are small enough to be easily sorted. The same process is applied to the M-Z pile.

Eventually, all the small sorted piles can be stacked one on top of the other to produce a sorted set of tests. (See Figure 7.7.)

Click To expand
Figure 7.7: Ordering a list using the quick sort algorithm

This strategy is based on recursion-on each attempt to sort the stack of tests, the stack is divided and then the same approach is used to sort each of the smaller stacks (a smaller case). This process continues until the small stacks do not need to be further divided (the base case). The parameter list of the Quicksort function reflects the part of the list that is currently being processed: We pass the array and the first and last indexes that define the part of the array to be processed on this call. The initial call to Quicksort is

QuickSort(values, 0, numberOfValues-1);

QuickSort

if there is more than one item in values[first]..values[last]
      Select splitVal
      Split the array so that
            values[first]..values[splitPoint-1] <= splitVal
            values[splitPoint] = splitVal
            values[splitPoint+1]..values[last] > splitVal
      QuickSort the left half
      QuickSort the right half

How do we select splitVal? One simple solution is to use the value in values[first] as the splitting value. (We show a better value later.)

Click To expand

After the call to Split, all items less than or equal to splitVal are on the left side of the array and all items greater than splitVal are on the right side of the array.

Click To expand

The two "halves" meet at splitPoint, the index of the last item that is less than or equal to splitVal. Note that we don't know the value of splitPoint until the splitting process is complete. We can then swap splitVal with the value at splitPoint.

Click To expand

Our recursive calls to Quicksort use this index (splitPoint) to reduce the size of the problem in the general case.

Quicksort (values, first, splitPoint - 1) sorts the left "half" of the array. Quicksort (values , splitPoint + 1, last) sorts the right "half" of the array. (The "halves" are not necessarily the same size.) splitVal is already in its correct position in values[splitPoint].

What is the base case? When the segment being examined has less than two items, we do not need to continue. So "there is more than one item in values [first]..values [last]" can be translated into "if (first < last)". We can now code the function Quicksort.

template<class ItemType>
void Quicksort(ItemType values[], int first, int last)
{
  if (first < last)
  {
    int splitPoint;

    Split(values, first, last, splitPoint);
    // values[first]..values[splitPoint-1] <= splitVal
    // values[splitPoint] = splitVal
    // values[splitPoint+1]..values[last] > splitVal

    QuickSort(values, first, splitPoint-1);
    QuickSort(values, splitPoint+1, last);
  }
}

Let's verify Quicksort using the Three-Question Method.

  1. Is there a nonrecursive base case? Yes. When first >= last (the segment contains at most one element), Quicksort does nothing.

  2. Does each recursive call involve a smaller case of the problem? Yes. Split divides the segment into two not necessarily equal pieces, and each of these smaller pieces is then quick sorted. Note that even if splitVal is the largest or smallest value in the segment, the two pieces are still smaller than the original one. If splitVal is smaller than all other values in the segment, then Quicksort (values, first, splitPoint - 1) terminates immediately, because first > splitPoint - 1. Quicksort (values, splitPoint + 1, last) quick sorts a segment one element smaller than the original.

  3. Assuming that the recursive calls succeed, does the entire function work? Yes. We assume that QuickSort(values, first, splitPoint - 1) actually sorts the first splitPoint - 1 elements, whose values are less than or equal to splitVal.values [splitPoint], which contains splitVal, is in its correct place. We also assume that Quicksort (values, splitPoint + 1, last) has correctly sorted the rest of the list, whose values are all greater than splitVal. In this way, we determine that the whole list is sorted.

In good top-down fashion, we have shown that our algorithm works if the function Split works. Now we must develop our splitting algorithm. We must find a way to get all elements equal to or less than splitVal on one side of splitVal and all elements greater than splitVal on the other side.

We achieve this goal by moving the indexes, first and last, toward the middle of the array, looking for items that are on the wrong side of the split point (Figure 7.8). We make first and last be value parameters, so we can change their values without affecting the calling function. We save the original value of first in a local variable, saveFirst. (See Figure 7.8a.)[2]

Click To expand
Figure 7.8: Function split

We start by moving first to the right, toward the middle, comparing values[first] to splitVal. If values[first] is less than or equal to splitVal, we keep incrementing first; otherwise, we leave first where it is and begin moving last toward the middle. (See Figure 7.8b.)

Now we compare values[last] to splitVal. If it is greater, we continue decrementing last; otherwise, we leave last in place. (See Figure 7.8c.) At this point, it is clear that values[last] and values[first] are each on the wrong side of the array. Note that the elements to the left of values[first] and to the right of values[last] are not necessarily sorted; they are just on the correct side with respect to splitVal. To put values[first] and values[last] into their correct sides, we merely swap them, then increment first and decrement last. (See Figure 7.8d.)

Now we repeat the whole cycle, incrementing first until we encounter a value that is greater than splitVal, then decrementing last until we encounter a value that is less than or equal to splitVal. (See Figure 7.8e.)

When does the process stop? When first and last meet each other, no further swaps are necessary. They meet at splitPoint, the location where splitVal belongs. We swap values[saveFirst], which contains splitVal, with the element at values[splitPoint] .(See Figure 7.8f.) The index splitPoint is returned from the function, to be used by Quicksort to set up the next recursive call.

void Split(ItemType values[], int first, int last, int& splitPoint)
{
  ItemType splitVal = values[first];
  int saveFirst = first;
  bool onCorrectSide;

  first++;
  do
  {
    onCorrectSide = true;
    while (onCorrectSide)             // Move first toward last.
      if (values[first] > splitVal)
        onCorrectSide - false;
      else
      {
        first++;
        onCorrectSide = (first <= last);
      }

    onCorrectSide = (first <= last);
    while (onCorrectSide)             // Move last toward first.
      if (values[last] <= splitVal)
        onCorrectSide = false;
      else
      {
        last--;
        onCorrectSide = (first <= last);
      }

    if (first < last)
    (
      Swap(values[first] , values [last]);
      first++;
      last--;
    }
  } while (first <= last) ;

  splitPoint = last;
  Swap(values[saveFirst], values[splitPoint]);
}

What happens if our splitting value is the largest or the smallest value in the segment? The algorithm still works correctly, but because of the lopsided splits it is not so quick.

Is this situation likely to occur? That depends on our choice of a splitting value and on the original order of the data in the array. If we use values[first] as the splitting value and the array is already sorted, then every split is lopsided. One side contains one element, while the other side contains all except one of the elements. Thus our QuickSort is not a quick sort. Such a splitting algorithm favors an array in random order.

It is not unusual, however, to want to sort an array that is already in nearly sorted order. In such a case, a better splitting value would be the middle value,

values[(first + last) / 2]

This value could be swapped with values[first] at the beginning of the function.

Many possible splitting algorithms exist. One that represents a slight variation of the one we have just developed is given below. It uses the value in the middle of the array as the splitting value without moving it to the first slot. As a result, the value in values[splitPoint] may or may not be in its permanent place.

void Split2(ItemType values[], int first, int last,
            int& splitPt1, int& splitPt2)
{
  ItemType splitVal = values[(first+last)/2];
  bool onCorrectSide;
  do
  {
    onCorrectSide = true;
    while (onCorrectSide)     // Move first toward last.
      if (values[first] >= splitVal)
        onCorrectSide = false;
      else
        first++;

    onCorrectSide = true;
    while (onCorrectSide)          // Move last toward first.
      if (values[last] <= splitVal)
        onCorrectSide = false;
      else
        last--;
    if (first <= last)
    {
      Swap(values[first], values[last]);
      first++;
      last--;
     }
  } while (first <= last);

  splitPt1 - first;
  splitPt2 = last;
}

If we use this algorithm, QuickSort must be adjusted slightly.

void QuickSort2(ItemType values[], int first, int last)
{
  if (first < last)
  {
    int splitPt1;
    int splitPt2;

    Split2(values, first, last, splitPt1, splitPt2);
    // values[first]..values[splitPt2] <= splitVal
    // values[splitPt1+1]..values[last] > splitVal

    if (splitPt1 < last)
      QuickSort2(values, splitPt1, last);
    if (first < splitPt2)
      QuickSort2(values, first, splitPt2);
  }
}

Notice that QuickSort2 makes the recursive call only if a segment contains more than one element. This approach makes the code more efficient. We will analyze the complexity of Quicksort when we analyze the other sorting algorithms in Chapter 10. We emphasize here merely that the algorithm is very sensitive to the choice of the splitting value.

[2]We assume that the relational operators are defined on values of ItemType.



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