Sorting
Five sorting algorithms, each sorting the same eight bars. Every editor starts afresh, so run them in any order and compare the counts at the top of the canvas.
Colors: amber bars are being compared, with amber dots under them, and teal bars are in their final place. Violet means something different in each algorithm, and each section says what.
The bars
Run this first. It draws the bars and defines the helpers the other editors use.
pie.clear()
heights = [5, 2, 7, 1, 6, 3, 8, 4]
n = len(heights)
gray, amber, violet, teal = '#a8a29e', '#fcd34d', '#c4b5fd', '#5eead4'
def x(slot):
"""The x position of slot `slot`."""
return slot - (n - 1) / 2
def setup(*names):
"""Draws the bars unsorted on a dark canvas, and a count for each of `names` at the top."""
global bottoms, tops, bars, order, pointers, dots, tick, counts
pie.text('#1c1917', out='canvasColor')
pie.scalar(0, out='gridOpacity')
bottoms = [pie.point(x(i), 0, hidden=True) for i in range(n)]
tops = [pie.point(x(i), h / 2, hidden=True) for i, h in enumerate(heights)]
bars = [pie.line(b, t, stroke=gray) for b, t in zip(bottoms, tops)]
order = list(range(n)) # bars[order[i]] is the bar in slot i
# Two amber dots under the bars being compared.
pointers = [pie.point(x(i), -0.5, hidden=True) for i in (0, 1)]
dots = [pie.circle(p, 0.15, fill=amber, stroke='none') for p in pointers]
tick = pie.scalar(0) # not drawn; animating it is a half-second pause
counts = {name: 0 for name in names or ('comparisons', 'swaps')}
add_count(None)
for _ in range(3): # a 1.5-second pause, to see the bars before they move
pie.translate_scalar_by(tick, 1, animate=True)
def add_count(name):
"""Adds 1 to count `name` (None: none) and shows the counts."""
if name:
counts[name] += 1
pie.text(', '.join(f'{k}: {v}' for k, v in counts.items()), 0, 5, 14, stroke='#e7e5e4', out='counts')
def height(slot):
return heights[order[slot]]
def color(slots, c):
pie.set_stroke([bars[order[s]] for s in slots], c)
def compare(i, j):
"""Turns the bars in slots i and j amber, glides the dots under them, and returns True if the bar in slot i is taller."""
add_count('comparisons')
color([i, j], amber)
pie.translate_point_to(pointers, [x(i), x(j)], [-0.5, -0.5], animate=True)
return height(i) > height(j)
def swap(i, j):
"""Slides the bars in slots i and j past each other."""
a, b = order[i], order[j]
d = j - i
pie.translate_point_by([bottoms[a], tops[a], bottoms[b], tops[b]], [d, d, -d, -d], 0, animate=True)
order[i], order[j] = b, a
add_count('swaps')
setup()
order tracks which bar is in which slot. A swap moves the two points of each of the two bars, and the bars follow. Each dot is a circle around a hidden point, so moving the point moves the dot.
Bubble sort
Walk along the row and swap every pair of neighbors that is in the wrong order. After each pass, the tallest bar left has reached its place at the end.
pie.clear()
setup()
for end in range(n - 1, 0, -1):
for i in range(end):
if compare(i, i + 1):
swap(i, i + 1)
color([i, i + 1], gray)
color([end], teal)
color([0], teal)
pie.hide(dots)
Each swap fixes exactly one pair of bars in the wrong order, so it makes 12 swaps here, like insertion sort. But it always makes 28 comparisons, the same as selection sort.
Selection sort
Find the shortest bar, and swap it into the first slot. Then find the shortest of the rest, swap it into the second slot, and so on. Violet marks the shortest bar found so far.
pie.clear()
setup()
for i in range(n - 1):
shortest = i
color([i], violet)
for j in range(i + 1, n):
if compare(shortest, j):
color([shortest, j], gray)
shortest = j
else:
color([j], gray)
color([shortest], violet)
if shortest != i:
swap(i, shortest)
color([i], teal)
color([n - 1], teal)
pie.hide(dots)
It always makes the same number of comparisons: 7 + 6 + … + 1 = 28 for 8 bars, however the bars start. But it makes at most one swap per slot.
Insertion sort
Take each bar in turn, and slide it left past every taller bar. Violet marks the bars on the left, which are sorted among themselves but may still move.
pie.clear()
setup()
color([0], violet)
for i in range(1, n):
j = i
while j > 0 and compare(j - 1, j):
swap(j - 1, j)
color([j], violet)
j -= 1
color(range(i + 1), violet)
color(range(n), teal)
pie.hide(dots)
Each swap fixes exactly one pair of bars in the wrong order, so it makes as many swaps as there are such pairs: 12 here. On bars that are almost sorted, that is very few.
Merge sort
Split the bars in half, sort each half, then merge the two sorted halves. Each half is sorted the same way, down to single bars. To merge, compare the first bar of each half and drop the shorter one into its place in the row below. When both halves are used up, the merged bars rise back.
pie.clear()
setup('comparisons', 'moves')
drop = 5 # how far below the row the merged bars wait
def merge(lo, mid, hi):
"""Merges the sorted slots lo to mid - 1 and mid to hi - 1."""
i, j = lo, mid
merged = []
for k in range(lo, hi):
if i < mid and j < hi:
take_right = compare(i, j)
color([i, j], gray)
else:
take_right = i == mid
s = j if take_right else i
if take_right:
j += 1
else:
i += 1
bar = order[s]
pie.set_stroke(bars[bar], violet)
pie.translate_point_by([bottoms[bar], tops[bar]], [k - s, k - s], [-drop, -drop], animate=True)
add_count('moves')
merged.append(bar)
order[lo:hi] = merged
pie.set_stroke([bars[bar] for bar in merged], gray)
points = [p for bar in merged for p in (bottoms[bar], tops[bar])]
pie.translate_point_by(points, [0] * len(points), [drop] * len(points), animate=True)
def merge_sort(lo, hi):
"""Sorts slots lo to hi - 1."""
if hi - lo < 2:
return
mid = (lo + hi) // 2
merge_sort(lo, mid)
merge_sort(mid, hi)
merge(lo, mid, hi)
merge_sort(0, n)
color(range(n), teal)
pie.hide(dots)
Violet bars have been merged and are waiting in the row below. There are 3 levels of halving for 8 bars, and each level moves every bar once: 24 moves. For bars that is about , which grows much more slowly than the comparisons of selection sort.
Quicksort
Pick a bar as the pivot: here, the last one. Move every bar shorter than it to the left, then put the pivot right after them. The pivot is now in its final place, so sort the bars on each side of it the same way. Violet marks the pivot, and the violet dot, below the amber ones, marks the slot where the next shorter bar goes.
pie.clear()
setup()
marker = pie.point(x(0), -1, hidden=True)
marker_dot = pie.circle(marker, 0.15, fill=violet, stroke='none')
def partition(lo, hi):
"""Moves the bars in slots lo to hi - 1 that are shorter than the pivot in slot hi to the left, then puts the pivot after them. Returns the pivot's slot."""
color([hi], violet)
store = lo
pie.translate_point_to(marker, x(store), -1, animate=True)
for j in range(lo, hi):
shorter = not compare(j, hi)
color([j], gray)
color([hi], violet)
if shorter:
if store != j:
swap(store, j)
store += 1
pie.translate_point_to(marker, x(store), -1, animate=True)
if store != hi:
swap(store, hi)
color([store], teal)
return store
def quick_sort(lo, hi):
"""Sorts slots lo to hi."""
if lo > hi:
return
if lo == hi:
color([lo], teal)
return
p = partition(lo, hi)
quick_sort(lo, p - 1)
quick_sort(p + 1, hi)
quick_sort(0, n - 1)
pie.hide(dots + [marker_dot])
Quicksort is fast when each pivot splits the bars roughly in half. With the last bar as the pivot, already sorted bars are the worst case: every split leaves one side empty, and it makes as many comparisons as selection sort.