Medium lo/mid/hi Pointers Sorting
In plain English: Sort an array containing only 0s, 1s, and 2s in a single pass.
Three pointers carve the array into four regions: 0s, 1s, unknown, and 2s — each swap shrinks the unknown region.
Prompt
Sort an array of 0s, 1s, and 2s in one pass.
Try to write it from scratch before scrolling down.
Solution
def dutch_flag(a):
lo, mid, hi = 0, 0, len(a) - 1
# 0: swap to lo, 2: swap to hi, 1: skip
while mid <= hi:
if a[mid] == 0:
a[lo], a[mid] = a[mid], a[lo]
lo += 1; mid += 1
elif a[mid] == 1:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1
return a
# Test: dutch_flag([2,0,1,2,1,0]) == [0,0,1,1,2,2]