Sort 0s, 1s and 2s in One Pass (Dutch National Flag)
An array contains only the values 0, 1 and 2. Sort it in place in a single pass with O(1) extra memory and without counting.
Implement void sort_012(int *a, size_t n).
Example: {2, 0, 2, 1, 1, 0} → {0, 0, 1, 1, 2, 2}.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Use three indexes: everything before low is 0, everything after high is 2, and mid scans the unknown middle. A 0 is swapped to low, a 2 is swapped to high, a 1 stays. After swapping with high, do not advance mid: the value you swapped in is still unchecked.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
void sort_012(int *a, size_t n)
{
if (n == 0) return;
size_t low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (a[mid] == 0) {
swap(&a[low++], &a[mid++]);
} else if (a[mid] == 1) {
mid++;
} else { /* a[mid] == 2 */
swap(&a[mid], &a[high]);
if (high == 0) break; /* avoid size_t underflow */
high--; /* mid stays: new a[mid] is unchecked */
}
}
}
Dijkstra's Dutch National Flag algorithm keeps four regions at all times:
[0 .. low-1] all 0s
[low .. mid-1] all 1s
[mid .. high] not yet examined
[high+1 .. n-1] all 2s
Each step shrinks the unknown region by one, so it is one pass, O(n) time, O(1) memory.
Walk-through: {2, 0, 2, 1, 1, 0}
| low | mid | high | a[mid] | action | array |
|---|---|---|---|---|---|
| 0 | 0 | 5 | 2 | swap mid↔high, high-- | 0 0 2 1 1 2 |
| 0 | 0 | 4 | 0 | swap low↔mid, low++, mid++ | 0 0 2 1 1 2 |
| 1 | 1 | 4 | 0 | swap low↔mid, low++, mid++ | 0 0 2 1 1 2 |
| 2 | 2 | 4 | 2 | swap mid↔high, high-- | 0 0 1 1 2 2 |
| 2 | 2 | 3 | 1 | mid++ | 0 0 1 1 2 2 |
| 2 | 3 | 3 | 1 | mid++ → done | 0 0 1 1 2 2 |
Why mid does not move after the 2-swap: the element brought in from high has not been examined yet; it could be a 0 that must still go left. After a 0-swap, the element coming from low is already known to be a 1 (or it is the same element), so mid can advance.
Watch out in C: with unsigned size_t indexes, high-- when high == 0 wraps to a huge number, so the solution stops explicitly. The original int version avoids this but cannot handle arrays larger than INT_MAX.
Follow-ups: counting sort (two passes) is simpler if a single pass is not required; the same partitioning is the core of three-way quicksort, which handles many duplicate keys efficiently; "move all zeros to the end" and "segregate even/odd" are two-region versions.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
int a[] = { 2, 0, 2, 1, 1, 0 };
const int ea[] = { 0, 0, 1, 1, 2, 2 };
sort_012(a, 6); CHECK(memcmp(a, ea, sizeof ea) == 0);
int b[] = { 2, 2, 2 };
sort_012(b, 3); CHECK(b[0] == 2 && b[2] == 2);
int c[] = { 2, 1, 0 };
const int ec[] = { 0, 1, 2 };
sort_012(c, 3); CHECK(memcmp(c, ec, sizeof ec) == 0);
int d[] = { 0 };
sort_012(d, 1); CHECK(d[0] == 0);
sort_012(NULL, 0);
int e[] = { 1, 2, 0, 2, 0, 1, 1, 0, 2, 0 };
const int ee[] = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 2 };
sort_012(e, 10); CHECK(memcmp(e, ee, sizeof ee) == 0);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}