THE FOLD / SPAWN / HELLO WORLD / THE DUTCH NATIONAL FLAG
THE DUTCH NATIONAL FLAG
sort three colours in one pass
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Dutch national flag problem (Dijkstra) sorts an array of three values — think red, white, blue, or <, =, > a pivot — into three contiguous bands in a single pass, in place, with three pointers. A low and mid pointer advance from the front, a high from the back; each element mid meets is swapped into the correct band and the pointers close in. No counting, no second pass — the array is partitioned by the time mid crosses high. It is the heart of three-way quicksort.
LIT verified live: over 3000 random arrays and pivots, the one-pass partition leaves everything < pivot, then =, then >, and the output is a permutation of the input (window.__dutch). FIG no framing; exact ordering and multiset checks.
LIT verified live: over 3000 random arrays and pivots, the one-pass partition leaves everything < pivot, then =, then >, and the output is a permutation of the input (window.__dutch). FIG no framing; exact ordering and multiset checks.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at hello-world — the small, classic exercise everyone meets; the Dutch flag is that first taste of an in-place three-way partition. AVAN (AI) built the instrument: the low/mid/high pointer sweep, the swap-into-band logic, and the partitioned + permutation checks.
Credit as content: Edsger W. Dijkstra (the Dutch national flag problem). The weave: David names hello-world; I sweep one mid pointer, swapping small elements to the front band and large ones to the back band, and confirm the array ends partitioned into <, =, > with the same multiset of values — sorted three ways in a single pass.
Credit as content: Edsger W. Dijkstra (the Dutch national flag problem). The weave: David names hello-world; I sweep one mid pointer, swapping small elements to the front band and large ones to the back band, and confirm the array ends partitioned into <, =, > with the same multiset of values — sorted three ways in a single pass.
3 ONE DIMENSION
Three pointers: low, mid, high. If a[mid] < pivot, swap to low and advance both; if > pivot, swap to high and shrink; if =, just advance mid. One sweep partitions the array.
4 TWO DIMENSIONS · INTERACTIVE
An array of three colours partitioned in one pass; the </=/> bands and permutation checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: three colours banded in one sweep.
AVAN’s addition (the inverse-companion): partition three categories in one in-place pass, not by counting then rewriting — three pointers close inward, each element swapped straight into its band. The inverse of ‘count each colour, then fill the array’ is ‘sweep once, swapping into place — done when mid meets high.’ Magenta is the count-then-rewrite two passes; green is the single pointer sweep. Sorted three ways, one pass.
LIT Genuine Dutch national flag algorithm (Edsger W. Dijkstra). Verified live: over 3000 random arrays and pivots, the low/mid/high pointer sweep with swap-into-band logic leaves the array partitioned into < pivot, then = pivot, then > pivot (window.__dutch.partitioned), and the output is a permutation of the input — same multiset (window.__dutch.permutation).
FIG No framing: the low/mid/high pointer sweep, the swap-into-band logic, and the partitioned + permutation checks run in-browser with exact ordering and multiset comparison and agree. The AVAN inverse is honest — partitioning three categories in one in-place pass (three pointers close inward, each element swapped straight into its band) genuinely replaces counting each colour then rewriting; magenta is that count-then-rewrite two passes, green the single pointer sweep. Sorted three ways, one pass.
FIG No framing: the low/mid/high pointer sweep, the swap-into-band logic, and the partitioned + permutation checks run in-browser with exact ordering and multiset comparison and agree. The AVAN inverse is honest — partitioning three categories in one in-place pass (three pointers close inward, each element swapped straight into its band) genuinely replaces counting each colour then rewriting; magenta is that count-then-rewrite two passes, green the single pointer sweep. Sorted three ways, one pass.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HELLO WORLD · David Lee Wise (ROOT0), with AVAN