Data Structures with Generic Types in Java/

...

/

Quicksort

Quicksort

Learn about quicksort and partitioning algorithms.

We'll cover the following...

The quicksort algorithm is another classic divide-and-conquer algorithm. Unlike merge-sort, which does merging after solving the two subproblems, quicksort does all of its work upfront.

Quicksort is simple to describe: Pick a random pivot element, x, from a; partition a into the set of elements less than x, the set of elements equal to x, and the set of elements greater than x; and, finally, recursively sort the first and third sets in this partition.

Visual demonstration

An example is shown in the following figure.

An example execution of quickSort(a,0,14,c)
An example execution of quickSort(a,0,14,c)

The implementation of the quickSort() method is:

< T > void quickSort(T[] a, Comparator < T > c) {

    quickSort(a, 0, a.length, c);

}

< T > void quickSort(T[] a, int i, int n, Comparator < T > c) {

    if (n <= 1) return;

    T x = a[i + rand.nextInt(n)];

    int p = i - 1, j = i, q = i + n;

    // a[i..p]<x,  a[p+1..q-1]??x, a[q..i+n-1]>x

    while (j < q) {

      int comp = compare(a[j], x);

      if (comp < 0) { // move to beginning of array

        swap(a, j++, ++p);

      } else if (comp > 0) {

        swap(a, j, --q); // move to end of array

      } else {

        j++; // keep in the middle

      }

    }

    // a[i..p]<x,  a[p+1..q-1]=x, a[q..i+n-1]>x

    quickSort(a, i, p - i + 1, c);

    quickSort(a, q, n - (q - i), c);

}

All of this is done in place, so that instead of making copies of subarrays being sorted, the quickSort(a, i, n, c) method only sorts the subarray a[i],...,a[i + n − 1]. Initially, this method is invoked with the arguments quickSort(a,0,a.length,c).

Partitioning algorithm

At the heart of the quicksort algorithm is the in-place partitioning algorithm. This algorithm, without using any extra space, swaps elements in a and computes indexes p and q so that

a[i]{<x  if 0≤i≤p=x  if p<i<q>x  if q≤i≤n−1a[i] \begin{cases} < x & \ \ \text{if $0 \leq i \leq p$}\\ = x & \ \ \text{if $p < i < q$}\\ > x & \ \ \text{if $q \leq i \leq n − 1$}\\ \end{cases} ...