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

Quicksort

Explore the quicksort algorithm and understand its divide-and-conquer strategy for sorting arrays in place. Learn how the partitioning algorithm works with pivots and discover the connection to random binary search trees. This lesson explains quicksort's expected performance and teaches how to implement it for efficient array sorting.

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.

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:

Python 3.10.4
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} ...