Algorithms / Partitioning Dutch Flag
Least You Need to Know: Partitioning Invariants and Dutch-Flag Regions
Partition algorithms maintain region invariants while scanning an unknown middle segment. This is the interview core behind quickselect-style partitioning, Dutch-flag sorting, and in-place grouping by a pivot or category.
The least you need to know
- A partition algorithm divides the array into solved regions and an unsolved region.
- The loop invariant says what each region already guarantees about its elements.
- When swapping with the high boundary in Dutch-flag partitioning, the current index may need to stay put and inspect the swapped-in value.
- Partitioning is about classification by comparison or category, not global sorting.
- A correct partition proof is really an invariant proof about shrinking the unknown region.
Key notation
< pivot | = pivot | unknown | > pivot
Dutch-flag region layout
low, mid, high
region boundaries for three-way partitioning
unknown region
segment not yet classified
Tiny worked example
- Keep `[0, low)` as values less than the pivot and `(high, end)` as values greater than the pivot.
- Let `mid` scan the unknown region.
- A small value swaps left and advances both `low` and `mid`.
- A large value swaps right and shrinks `high`, but `mid` stays to inspect the new value.
Common mistakes
- Students often advance `mid` after swapping with `high`, skipping the new unclassified value.
- Students often confuse partitioning with full sorting.
- Students often describe swaps but not the region invariant that proves correctness.
How to recognize this kind of problem
- The prompt asks to group values by a pivot, color, or predicate in place.
- There is an unknown middle region that shrinks over time.
- The output only needs correct grouping, not total sorted order.