Dutch-flag with three pointers
Updated
low, mid, high split three buckets. mid scans. a[mid] < pivot: swap with low, low++, mid++. a[mid] == pivot: mid++. a[mid] > pivot: swap with high, high-- (mid stays). Stop when mid > high.
What to focus on
[0, low) are < pivot. [low, mid) are == pivot. (high, n-1] are > pivot. [mid, high] is unknown.
Worked examples
colors
a = [2, 0, 1], pivot 1, low=0 mid=0 high=2- 2>1 swap with high → [1, 0, 2], high=1
- 1==1 mid=1
- 0<1 swap with low → [0, 1, 2], low=1 mid=2
Result: [0, 1, 2]
around 4
a = [1, 9, 1, 4], pivot 4, low=0 mid=0 high=3- 1<4 swap low/mid → low=1 mid=1
- 9>4 swap mid/high → [1, 4, 1, 9], high=2
- 4==4 mid=2
- 1<4 swap → [1, 1, 4, 9]
Result: [1, 1, 4, 9]
zeros and ones
a = [0, 1, 0, 9], pivot 1, low=0 mid=0 high=3- 0<1 → low=1 mid=1
- 1==1 mid=2
- 0<1 swap → [0, 0, 1, 9], low=2 mid=3
- 9>1 swap high, mid>high
Result: [0, 0, 1, 9]
Try it
Write dutchFlag(a, pivot). a is an array of integers. pivot is a value that appears in a or splits the range. low, mid, and high are indices. Return the partitioned array. On [2, 0, 1] pivot 1 and [1, 9, 1, 4] pivot 4.
a is nonempty, length ≥ 2. pivot is a value that appears in a or splits the range.