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.

Press + to interact
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:

Press + to interact
< 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} ...