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:
B. Order of 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 list 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.
This is the code for quicksort:
first, int last)
int g = first, h = last;
int midIndex, dividingValue, temp;
midIndex = (first + last) / 2;
dividingValue = list[midIndex];
while (list[g] < dividingValue) g++;
while (list[h] > dividingValue) h--;
if (g <= h)
while (g < h);
if (h > first) quickSort (list,first,h);
if (g < last) quickSort (list,g,last);
3. Suppose we have the following list of 9 unsorted values in an array:
17 22 34 28 19 84 11 92 1
b. The midIndex value is calculated as (1+9) / 2, which equals 5.
c. The dividingValue is the value in location 5, list = 19.
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 and list 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.
1. Determining the order of quicksort, O (N*log2N), is a difficult process. The best way to understand it is to imagine a hypothetical situation where each call of quicksort results in even sublists.
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).
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.
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.