Quicksort

Internal

• Algorithms
• Sorting Algorithms
• The Partition Subroutine

Overview

In-place sorting divide-and-conquer algorithm. Being an in-place sorting algorithm is considered preferable to merge sort, which has to allocate extra memory.

Worst-case time	Θ(n2)
Expected running time	Θ(n lgn)
Best-case time	Θ(n lgn)

Algorithm

The procedure receives the reference to the array containing the numbers to be sorted, and the edges p (the first element of the section to be sorted) and r (the element immediately following the last element to be sorted, or the outside of the array). As all divide-and-conquer algorithms, Quicksort has three steps:

1. Divide: it partitions the area to be sorted in three zones, possibly empty: 1) the left zone a[p ... q-1] contains numbers smaller or equal with a special element, called pivot, 2) one zone with one element a[q] containing the pivot 3) the right zone a[q +1 ... r-1], possibly empty that contains numbers bigger or equal with the pivot.
2. Conquer: applies itself recursively on the subarray containing the left zone and on the subarray containing the pivot and on the right zone.
3. Combine: since the zones are already sorted, there is nothing to combine.

/**
 * @param p the index of the first element of the array to be sorted (subarray of int[] a)
 * @param r the index of the first element *outside* the area to be sorted.
 **/
public void quicksort(int[] a, int p, int r) {

    if (p < r - 1) {

        int q = partition(a, p, r);

        quicksort(a, p, q);
        quicksort(a, q, r);
    }
}

/**
 * @param p the index of the first element of the array to be sorted (subarray of int[] a)
 * @param r the index of the first element *outside* the area to be sorted.
 **/
private int partition(int[] a, int p, int r) {

    int pivot = a[r - 1];

    int i = p - 1;

    for(int j = p; j < r - 1; j ++) {

        if (a[j] <= pivot) {

            i = i + 1;

            //
            // swap i, j
            //

            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    //
    // swap i + 1 and the pivot
    //

    int q = i + 1;

    int tmp = a[q];
    a[q] = a[r - 1];
    a[r - 1] = tmp;

    return q;
}

Example

Playground Quicksort

Time Complexity Analysis

CLRS pages 174, 180. TODO:

• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/sIY1s/analysis-ii-the-key-insight

Quicksort and Selection Problem

The randomized Quicksort algorithm is somewhat similar to the one used by the generic selection problem.