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.
476 1066 1492 1776 1812 1945 1984 2001 2019
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)
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)):
1945 1984 1812 2001 2019 1776 1492 1066 476
quicksort
function sort a
list
or
tuple
of
str
ings?