Quicksort.
Quicksort. (source: Simpsons contributor on Wikimedia Commons)

100 Days of Algorithms is a series of Medium posts and Jupyter Notebooks by Tomáš Bouda that implement 100 interesting algorithms. They're a programming exercise that Bouda set for himself: can he implement 100 interesting algorithms, one per day?

The answer was “yes.” The algorithms range from classics like Towers of Hanoi to Bloom filters and graph traversal. Over the coming weeks, we’ll be featuring selections from Bouda's 100 Days of Algorithms project here on O’Reilly.

Day 57, Quicksort

Quicksort is the sorting algorithm used in almost every programming library. It's very fast—probably the fastest general purpose sort out there. As Bouda points out in his post on Medium, it's more than a bit scary: getting it right is tricky, and there are a lot of unexpected worst cases. You'll probably never need to implement this, but it's worth seeing how it's done.

Here's Bouda's Medium post, and you can access and clone the Jupyter Notebook here.

import numpy as np

algorithm

def swap(data, i, j):
    data[i], data[j] = data[j], data[i]
def qsort3(data, left, right):
    # sorted
    if left >= right:
        return

    # select pivot
    i = np.random.randint(left, right + 1)
    swap(data, left, i)
    pivot = data[left]

    # i ~ points behind left partition
    # j ~ points ahead of right partition
    # k ~ current element
    i, j, k = left, right, left + 1

    # split to [left] + [pivot] + [right]
    while k <= j:
        if data[k] < pivot:
            swap(data, i, k)
            i += 1
        elif data[k] > pivot:
            swap(data, j, k)
            j -= 1
            k -= 1
        k += 1

    # recursion
    qsort3(data, left, i - 1)
    qsort3(data, j + 1, right)
def qsort(data):
    qsort3(data, 0, len(data) - 1)

run

data = np.random.randint(0, 10, 100)
print(data)
[6 1 7 9 9 9 9 8 7 6 9 9 6 3 5 4 1 8 1 7 0 1 9 3 1 0 3 2 4 3 1 7 6 0 2 7 0
 7 9 1 0 4 9 2 3 4 5 9 5 8 9 1 8 2 0 5 4 9 5 3 1 0 1 1 2 3 8 1 4 2 2 4 7 9
 3 0 0 4 9 3 0 7 0 8 5 8 3 5 9 6 7 6 5 9 3 4 0 1 0 7]

qsort(data)
print(data)
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3
 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7
 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9]

Technical notes

The implementations work; the Jupyter Notebooks all run. Since this started off as a personal exercise, don't expect the implementations to be optimal, bullet-proof, or even necessarily correct (though we don't see anything wrong with them). And don't expect them to contain your favorite algorithms (or the ones you need for your homework assignments).

The easiest way to install Jupyter Notebooks is to use Anaconda. The second easiest (and most bulletproof) way is to install Docker and then use the scipy-notebook container.

If you're rolling your own Jupyter environment, you need:

Article image: Quicksort. (source: Simpsons contributor on Wikimedia Commons).