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.
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
Worked example
- Keep
[0, low)as values less than the pivot and(high, end)as values greater than the pivot. - Let
midscan the unknown region. - A small value swaps left and advances both
lowandmid. - A large value swaps right and shrinks
high, butmidstays to inspect the new value.
Common mistakes
- Students often advance
midafter swapping withhigh, 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Permutations, Used Sets, and Constraint Propagation.
Least You Need to Know: Permutations, Used Sets, and Constraint PropagationRelated lessons
Keep going with nearby lessons in the same topic.