Quicksort

The quicksort algorithm (strategy) has been around since 1961, but I’ve never seen any language in which it can be written as simply as in Python.

Lines 29–32 of the quicksort function do part of the job. They divide the numbers into three categories: the numbers less than the pivot item, the ones equal to the pivot item, and the ones greater than the pivot item. Then line 33 calls the quicksort function (twice) to do the rest of the job, and pastes together the finished pieces with plus signs. And before any of this happens, lines 26–27 make sure that quicksort returns immediately if the job is already finished.

quicksort.py

Things to try

To see what the algorithm is doing, pass an extra argument to the quicksort function and print both arguments.

def quicksort(a, level):
    "Return a sorted list of the items in a."
    assert (isinstance(a, list) or isinstance(a, tuple)) and isinstance(level, int)
    print(level, a)

    if len(a) <= 1:
        return a   #a is already in order.

    pivot = a[len(a) // 2]   #the middle item
    smallValues  = [item for item in a if item <  pivot]
    mediumValues = [item for item in a if item == pivot]
    bigValues    = [item for item in a if item >  pivot]
    return quicksort(smallValues, level + 1) + mediumValues + quicksort(bigValues, level + 1)


for year in quicksort(years, 0):
    print(year)

The value of the pivot item is 1984. The yellow text (starting at level 1) is output as a side effect of sorting all the numbers that are less than 1984. The orange text (starting at level 1) is output as a side effect of sorting all the numbers that are greater than 1984.

0 (1492, 1776, 1066, 1812, 1984, 2001, 476, 2019, 1945)
1 [1492, 1776, 1066, 1812, 476, 1945]
2 [1492, 1776, 1066, 476]
3 [476]
3 [1492, 1776]
4 [1492]
4 []
2 [1945]
1 [2001, 2019]
2 [2001]
2 []
476
1066
1492
1776
1812
1945
1984
2001
2019

Here’s a way you can print the same level numbers without adding that second argument to quicksort.

import traceback

#immediately before the for loop
startingLevel = len(traceback.extract_stack()) + 1

    #immediately after the assert
    print(len(traceback.extract_stack()) - startingLevel, a)

Sort the numbers in increasing order of how far they are from 1900. To make the keyword argument key of quicksort optional, we had to provide a default value for it. This default value is a function (written as a lambda function) that simply returns its argument unchanged.

def quicksort(a, key = lambda item: item):
    "Return a sorted list of the items in a."
    assert isinstance(a, list) or isinstance(a, tuple)

    if len(a) <= 1:
        return a   #a is already in order.

    pivot = a[len(a) // 2]   #the middle item
    smallValues  = [item for item in a if key(item) <  key(pivot)]
    mediumValues = [item for item in a if key(item) == key(pivot)]
    bigValues    = [item for item in a if key(item) >  key(pivot)]
    return quicksort(smallValues, key = key) + mediumValues + quicksort(bigValues, key = key)


def score(year):
    "Return the distance between the year and 1900."
    return abs(year - 1900)


for year in quicksort(years, key = score):
    print(year)

Better yet,

for year in quicksort(years, key = lambda item: abs(item - 1900)):

Will our quicksort function sort a list or tuple of strings?