INTRODUCTION:

Quicksort is another recursive sorting algorithm that works by dividing lists in half. Whereas mergesort divided lists in half and then sorts 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 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.

2. This is the code for quicksort:

void quickSort (int[] list, int first, int last)
{
	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]);
      int temp = list[g];
      list[g] = list[h];
      list[h] = temp;
      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

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 values in list[2] and list[9] are swapped. After the values are swapped, 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.

B. Order of Quicksort

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.

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.