Quicksort

Internal

• Algorithms
• Sorting Algorithms
• The Partition Subroutine

Overview

Quicksort is an 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 lg n)
Best-case time	Θ(n lg n)

Algorithm

The key idea of Quicksort is to partition an array around a pivot. The pivot is chosen randomly and it can be formally shown that randomly choosing a pivot at each step of the algorithm produces an O(n lg n) time complexity on average.

Complexity

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

QuickSort does not subdivide the problem in equal subproblems at one level, so the master theorem does not apply in its current form.

CLRS pages 174, 180.

TODO Stanford algorithm class:

• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/5Tuvu/analysis-i-a-decomposition-principle
• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/sIY1s/analysis-ii-the-key-insight
• https://www.coursera.org/learn/algorithms-divide-conquer/lecture/aqD1O/analysis-iii-final-calculations

Quicksort and Selection Problem

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