Data Structures with Generic Types in Python/

...

/

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 figure.

Press + to interact
An example execution of quick_sort(a,0,14,c)
An example execution of quick_sort(a,0,14,c)

The implementation of the quick_sort() method is:

Press + to interact
def quick_sort(a):

    _quick_sort(a, 0, len(a))



def _quick_sort(a, i, n):

    if n <= 1: return

    x = a[i + _random_int(n)]

    (p, j, q) = (i-1, i, i+n)

    while j < q:

        if a[j] < x:

            p += 1

            a[j], a[p] = a[p], a[j]

            j += 1

        elif a[j] > x:

            q -= 1

            a[j], a[q] = a[q], a[j]

        else:

           j += 1

    _quick_sort(a, i, p-i+1)

    _quick_sort(a, q, n-(q-i))

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

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