The problem
Sort a list of 0s, 1s and 2s (red, white, blue) in one pass and in place.
Input: [2, 0, 2, 1, 1, 0, 2, 0] Output: [0, 0, 0, 1, 1, 2, 2, 2]
Picture it
Picture marbles being sorted into three zones by three pointers: left of lo is red, between lo and mid is white, right of hi is blue. mid scans the unknown middle: red swaps to the lo zone, blue swaps to the hi zone, white just moves on.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Dutch national flag: three pointers, one pass. O(n), O(1).
Python solution
def sort_colors(a): # 0 red, 1 white, 2 blue
lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
if a[mid] == 0:
a[lo], a[mid] = a[mid], a[lo]
lo, mid = lo + 1, mid + 1
elif a[mid] == 1:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1
return aIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.