QuickSort

QuickSort  was first developed by C.A.R. Hoare. It requires the picking of a partition element (pivot) and then partially sorting the array about the partition. You can then sort each of the two partitions by recursive application of the same technique. The algorithm can sort quite rapidly, but it can also sort very slowly [O(n^2) worst case].

QuickSort is a fast divide-an-conquer algorithm when comparison sorting arrays in place (frequently O(n log n)).

The basic algorithm for QuickSort is recursive and consists of the following steps:

  1. If the number of elements is 0 or 1, return.
  2. Pick any element and call it the pivot.
  3. Partition remaining elements into two disjoint groups called L and R.
  4. Return the result of QuickSort(L), followed by the pivot, followed by QuickSort(R).
The pivot divides array elements into two groups: those smaller than the pivot and those larger than the pivot.

The partition step places every element except the pivot in one of two groups.

   13  81 43  92  31  65  57  26  75  0

   Assume 65 is selected as the pivot.  Partition the elements.

    Left:  13  43  31  57  26  0
   Right:  81  92  75

   Quicksort the left items.  Quicksort the right items.
   0  13  26  31  43  57      75  81  92
                          65
Example:
   Original list:
      8  1  4  9  6  3  5  2  7  0

   Select the pivot  6  and swap the pivot with the last element.

      8  1  4  9  0  3  5  2  7  6

   Run   i  from left-to-right, and  j  from right-to-left.
   When  i  sees a large element,  i  stops.  When  j  sees
   a small element,  j  stops.  If  i  and  j  have not
   crossed, swap their items and continue; otherwise, stop
   this loop.

      i  stops at element 8; j stops at element 2
      the 8 and 2 are swapped

   2  1  4  9  0  3  5  8  7  6

      i  stops at element 9; j stops at element 5
      the 9 and 5 are swapped

   2  1  4  5  0  3  9  8  7  6

      i  stops at element 9; j stops at element 3
      i and j have crossed -- swap pivot with
      i'th element (6 with 9)

   2  1  4  5  0  3  6  8  7  9
Picking the pivot is important to good performance. Never choose the first element as the pivot (you should also avoid the last element). The middle element is usually a reasonable choice. The perfect pivot is one that results in equally sized partitions. Picking a random pivot has proven efficient.

The  median-of-three  is a popular technique for picking a pivot. Sort the first, middle and last elements of the list and use the median (in this case middle) value. Using this technique is good because while in the process of determining the pivot, you are also getting started on the sorting of the list (element 0 will be less than the pivot and element N-1 will be greater than the pivot).

QuickSort pseudo-code:

   quickSort(T a[], int left, int right) 

      if (left >= right) return;
      SWAP (a, left, (left+right)/2);
      last = left;
      for (i = left+1; i <= right; i++) {
         if (COMPARE (a, i,  left) {
            ++last;
            SWAP (a, last, i);
         }
      }

      SWAP (a, left, last);

      quickSort(a, left, last-1);
      quickSort(a, last+1, right);