CSC 241- Set #12


Quick Sort

Quicksort is a divide and conquer method of sorting similar to the mergeSort algorithm in out . It works by partitioning a list into two parts, then sorting the parts independently. The Algorithm has the following recursive structure:

void quickSort (int leftIndex, int rightIndex) {
   if (rightIndex>leftIndex) {
      int i = partition(leftIndex, rightIndex);
   quickSort(leftIndex,i-1);
   quickSort(i+1,rightIndex);
   }
}

The parameters leftIndex and rightIndex delimit the sublist within the original list that is to be sorted. We initiate the sort process by calling this method via quickSort(0,n-1), where n is the number of elements in the list. Similar to Selection sort it is assumed that the list of elements is available to us in this method and the partition method. The crux of the method is the partition method which must rearrange the list to make the following three conditions hold:

  1. the element data[i] is in its final place in the array for some i,
  2. all elements in data[leftIndex],...,data[i-1] are less than or equal to data[i],
  3. all elements in data[i+1],...,data[rightIndex] are greater than or equal to data[i].

partition

All implementations of partition require the notion of a pivot value. Pivot is chosen from the sublist of elements to be sorted. You could arbitrarily choose any element you want to act as the pivot, left most element, right most element, or as we will, the element in the middle. Our algorithm moves the pivot value to the location it belongs in the completely sorted list and all elements smaller than or equal to it fall in the left partition and the rest in the right partition. This way, when we apply the same algorithm to the left sublist and the right sublist and sort them both, the whole list is sorted.

Once we have a pivot value, we scan the list from the leftIndex until an element greater than or equal to pivot is found. we then scan from rightIndex until an element less than or equal to pivot is found. The two elements which stopped the scans are exchanged. We continue these left and right scans until the indexes meet each other. The pivot value will end up in it final position. Here is one implementation partition.

int partition (int leftIndex,int rightIndex) {
   int i = leftIndex;
   int j = rightIndex;
   int pivot = data[(leftIndex + rightIndex)/2];
   do {
        while(data[i] < pivot) i++;
        while(pivot < data[j]) j--;
        if (i < j) {
           int tmp = data[i];
           data[i] = data[j];
           data[j] = tmp;
        }
   } while (i < j);
   return i;
}



Consider this list and follow the trace shown when the partition is applied during the initial call to quickSort:

leftIndex=0, rightIndex=3, pivot=12
      -------------------      -------------------      -------------------
     |11 | 12  | 9  | 10 |==>|11 | 10  | 9  | 12 |==>  |11 | 10  | 9  | 12 | 
      -------------------     -------------------      --------------------
       0    1    2    3        0    1    2    3         0    1     2    3      
    i=0^           j=3^          i=1^      j=3^                    j=i=3^

Note that 12 (the pivot value) is in the correct spot (at the end of the list).

Once the value of i which 3 in this case is returned to the quickSort method, we call quickSort recursively with 0 and 2 for our left and right indices respectively.

leftIndex=0, rightIndex=2, pivot=10
     --------------     --------------     --------------
    |11 | 10  | 9  |==>| 9 | 10  |11  |==>| 9 | 10  |11  |
     --------------     --------------     --------------
      0    1    2        0    1    2        0    1    2   
    i=0^     j=2^     i=0^      j=2^        i=j=1^

Note that 10, the pivot value, is in the correct spot, the element to its left is smaller and the element to its right is larger. i is returned as 1.

Both recursive calls at this point will return without doing anything as the considered sublists in each case only contain one element.

The sublist from 0 to 2 is sorted, thus, we return back to quickSort and call the it again with 4 and 3 as the left and right indices respectively; which means nothing happens.

leftIndex=0, rightIndex=3, pivot=12
      ------------------- 
     | 9 | 10  |11  | 12 |         final!
      ------------------- 
       0    1    2    3   

Analysis of Quick Sort

quickSort is an O(nlog2n) algorithm. Sort Applet Demo is design to show some sort algorithms working side by side. quickSort is compared against a couple of versions of bubble sort that is a O(n2) algorithm.

I downloaded this Sort Applet from the web, it is designed to show how a number of different sort algorithms work. Be aware that you need a big screen for this one!

Why is quickSort O(nlog2n)? It is easy to show mathematically for the best case where we can always break the list in half:
n + 2 . 1/2 . n + 4 . 1/4 . n + ... + 2log(n-1) . 1/2log(n-1) . n =
n + n + n + ... + n

How many ns are there? log2n. Thats the reason for O(nlog2n).

Empirically, it has been shown that quick sort performs very close to nlog2n even in average cases.

Why is nlog2n vs. n2 important? With n as 1000, quick sort requires about 10,000 cell visits whereas selection sort requires 1000,000 visits. As n gets larger this difference becomes more and more pronounced.