Sort an array containing only 0s, 1s, and 2s in a single pass (the Dutch National Flag problem).
Maintain three pointers: low, mid, and high. Scan with mid: a 0 swaps to the low region (advance low and mid), a 2 swaps to the high region (advance high, do not advance mid), a 1 just advances mid. One pass, O(n) time, O(1) space — better than counting or general sorting.
public static void sort012(int[] a) {
int low = 0, mid = 0, high = a.length - 1;
while (mid <= high) {
if (a[mid] == 0) { int t = a[low]; a[low++] = a[mid]; a[mid++] = t; }
else if (a[mid] == 1) mid++;
else { int t = a[high]; a[high--] = a[mid]; a[mid] = t; }
}
}function sort012(a) {
let low = 0, mid = 0, high = a.length - 1;
while (mid <= high) {
if (a[mid] === 0) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; }
else if (a[mid] === 1) mid++;
else { [a[high], a[mid]] = [a[mid], a[high]]; high--; }
}
return a;
}def sort012(a):
low = mid = 0
high = len(a) - 1
while mid <= high:
if a[mid] == 0:
a[low], a[mid] = a[mid], a[low]
low += 1; mid += 1
elif a[mid] == 1:
mid += 1
else:
a[high], a[mid] = a[mid], a[high]
high -= 1
return aThe Dutch-flag partition underlies quicksort’s three-way partitioning and any "bucket into three ordered groups in one pass" task.
After swapping a[mid] with a[high], why must you NOT advance mid?