This Radix Sort lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
Radix sort groups integers by one digit at a time, starting from the ones place.
Each pass must be a stable grouping, or later digits undo the earlier ones.
Example 1: Start here
This version sorts non-negative integers.
def radix(items): # define the function; it runs when you call it
items = items[:] # a separate copy
exp = 1 # a whole number
while max(items) // exp > 0: # keep repeating while this stays true
buckets = [[] for _ in range(10)] # a list; the values stay in this order
for n in items: # repeat the indented lines once per value
buckets[(n // exp) % 10].append(n) # add one item at the end of the list
items = [n for bucket in buckets for n in bucket] # a list; the values stay in this order
exp *= 10 # update the stored value
return items # send this value back to the caller
print(radix([170, 45, 75, 90, 24, 2, 66]))
Example 2: Walk the values
Radix Sort starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [34, 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 = [34, 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? Radix Sort builds on that question.
values = [3, 34, 11] # a list; the values stay in this order
target = 34 # a whole number
print(target in values) # in is True when the value is found
This version sorts non-negative integers.
