This Quick Sort lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
Quick sort picks a pivot and builds two lists: values up to the pivot, and values above it. It then sorts those lists the same way.
The version here uses extra lists so the steps stay visible. An in-place version uses less memory.
Example 1: Start here
A pivot that is always the smallest item makes this as slow as a simple scan.
def quick(items): # define the function; it runs when you call it
if len(items) < 2: # run the indented lines only when this is true
return items # send this value back to the caller
pivot = items[0] # the first value
low = [n for n in items[1:] if n <= pivot] # a list; the values stay in this order
high = [n for n in items[1:] if n > pivot] # a list; the values stay in this order
return quick(low) + [pivot] + quick(high) # send this value back to the caller
print(quick([4, 1, 3, 2]))
Example 2: Walk the values
Quick Sort starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [31, 3, 11, 7] # a list; the values stay in this order
for value in values: # repeat the indented lines once per value
print(value)
Example 3: Keep the largest
Many data-structure lessons reduce a list to one answer. This one remembers the largest number seen so far.
values = [31, 3, 11, 7] # a list; the values stay in this order
best = values[0] # the first value
for value in values: # repeat the indented lines once per value
if value > best: # run the indented lines only when this is true
best = value # another name for the same value
print(best)
Example 4: Search for a target
A search asks one yes-or-no question: is the target in the collection? Quick Sort builds on that question.
values = [3, 31, 11] # a list; the values stay in this order
target = 31 # a whole number
print(target in values) # in is True when the value is found
A pivot that is always the smallest item makes this as slow as a simple scan.
