Computer Science - C++ Lesson 23:  Quicksort

INTRODUCTION:            Quicksort is another recursive sorting algorithm that works by dividing lists in half.  Whereas mergesort divided lists in half and then sorted each sublist, quicksort will roughly sort the entire list, and then split the list in half.  The order of these two sorts falls into a new category, O(N * log N).  When the lists become large, either of these sorts will do an excellent job.

The key topics for this lesson are:

A.      Quicksort     

B.      Order of Quicksort

VOCABULARY:            QUICKSORT           

DISCUSSION:      A.      Quicksort

1.      Here is the overall strategy of quicksort:

a. Quicksort chooses an arbitrary value from somewhere in the list.  A common location is the middle value of the list.

b. This value becomes a decision point for roughly sorting the lis­t into two sublists.  All the values smaller than the dividing value end up in the left sublist, while all the values greater than the dividing value end up in the right sublist.

c. Each sublist is then recursively sorted with quicksort.

d. The termination of quicksort occurs when a list of one value is obtained, which by definition is sorted.

 2.      This is the code for quicksort:

        int g = first, h = last;

        int midIndex, dividingValue, temp;

        midIndex = (first + last) / 2;

        dividingValue = list[midIndex];

        do

        {

                while (list[g] < dividingValue) g++;

                while (list[h] > dividingValue) h--;

                if (g <= h)

                {

                        swap(list[g], list[h]);

                        g++;

                        h--;

                }

        }

        while (g < h);

        if (h > first) quickSort (list,first,h);

        if (g < last) quickSort (list,g,last);

}

            17            22            34            28            19            84            11            92            1

  a. The values received by the formal parameter list in the first call of quicksort are a reference to an array, 1, and 9.  Variable first is initialized with the value 1, and last is initialized with the value 9.

 b. The midIndex value is calculated as (1+9) / 2, which equals 5.

 c. The dividingValue is the value in location 5, list[5] = 19.

  d. The value of 19 will be our decision point for sorting values into two lists.  The list to the left will contain all the values less than or equal to 19.  The list the right will contain the values larger than or equal to 19.  Or simply put, small values go to the left and large values go to the right.

e. The identifiers g and h will be indices to locations in the list.  The while loops will move g and h until a value is found to be on the wrong side of the dividing value of 19.  The g index is initialized with the value of first and the h index is initialized with the value of last. 

f. The g index starts at position 1 and moves until it “sees” that 22 is on the wrong side.  Index g stops at location 2. 

g. The h index starts at position 9.  Immediately it “sees” that the value 1 is on the wrong side.  Index h never moves and stays at position 9 of the array.

h.Since g <= h (2 <= 9), the swap function is called and the values in list[2] and list[9] are swapped.  After swap has been called, index g moves one position to the right and index h moves one position to the left. 

i. The values of the pointers are now:  g = 3, h = 8.   We continue the do-while loop until g and h have passed each other, that is when g < h.  At this point, the lists will be roughly sorted, with values smaller than 19 on the left, and values greater than 19 on the right.

j. If the left sublist has more than one value, (which is determined by the h>first expression), then a recursive call of quicksort is made.  This call of quicksort will send the index positions which define that smaller sublist.

k. Likewise, if the right sublist has more than one value, quicksort is called again and the index positions which define that sublist are passed.

  2.      If a list has 128 elements, the number of calls of quicksort required to move a value into its correct spot is log2128, which equals 7 steps.  Dividing the list in half gives us the log2N aspect of quicksort.

  3.      But we need to do this to 128 numbers, so the approximate number of steps to sort 128 numbers will be 128 * log2 128. 

      A general expression of the order of quicksort will be

      O(N * log2N).  An O(N * log2N) algorithm is a more specific designation of the broader category called O(N * log N). 

4.      A graph of an O(N*log2N) algorithm is very close to a linear algorithm.  The log2N number of steps grows very slowly making quicksort a dramatic improvement over the O(N2) sorts. 

SUMMARY/REVIEW:            Quicksort is generally the fastest and therefore most widely used sorting algorithm.  There is a variation of quicksort named "quickersort" but it is still in the same class of algorithms.  Once again, recursion makes fast work of a difficult task.

Worksheet: W.A.23-1 QUICKSORT

1.   Given the following list of unsorted data, determine the following results for the first call of quicksort.  Assume that the values are stored in positions 1 to 9 of an array.

      24    18    43    24    20    56    65     7    31

      a.   The DividingValue = _______

b.   Show the arrangement of the values in the array after the first call of quicksort is completed, but before it has made any recursive calls of quicksort.  Draw a line where the list will be separated into two sublists.

c.   Now when quicksort makes its first recursive calls, determine the values in the parameter lists when the first recursive calls are made:

      if (h > first)  quickSort (list, first, h);

                        first = _______            ;            h = ________

      if (g < last)  quickSort (list, g, last);

                        g = ________            ;            last = _________

2.      Explain how the order of quicksort is derived.