Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Java

Quicksort

Explore how quicksort sorts arrays by selecting a pivot, partitioning elements, and recursively sorting subarrays. Understand its in-place partitioning process and expected efficiency, enhancing your grasp of sorting algorithms in Java.

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:

Java
< 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} ...