Dutch national flag partition

Why this matters

Some lists hold only a few kinds of value. A survey might code each answer as 0 for no, 1 for maybe and 2 for yes. A game might store each card as one of three suits. A photo filter might map each pixel to one of three colour groups. You often want all the 0s first, then all the 1s, then all the 2s. This is a sort, and it is a small one, because there are only three values to order.

There is a simple way to do it. Count how many 0s, 1s and 2s there are, then write them back in order. That takes two passes over the list. This lesson shows a method that does the whole job in one pass, using three pointers and no extra counting. The problem is named after the three bands of the Dutch flag. The counting method is covered in the counting arrays lesson, and the general sorting methods are in the sorting module.

A pointer here means a number that stores an index. It is not the C++ pointer type from the pointers module. The three pointers are plain size_t variables that point at positions in the array. The lesson is about the logic, and the examples use vector<int> with the usual size() and swap functions.

The idea: three regions and three markers

Think of a row of cards on a table. Each card shows a 0, a 1 or a 2. You want to sort the row. Instead of picking cards up one at a time, you keep the row split into four parts, and you move the boundaries between the parts.

index:   0 .. lo-1 | lo .. mid-1 | mid .. hi-1 | hi .. n-1
region:     zeros   |    ones     |  not seen   |    twos

The three markers are called lo, mid and hi. Each one is a position in the array.

• Everything before lo is a 0.
• Everything from lo up to mid is a 1.
• Everything from mid up to hi has not been looked at yet.
• Everything from hi to the end is a 2.

At the start, the "not seen" part is the whole array. The zeros and ones regions are empty, and the twos region is empty. Each step looks at the card under mid, which is the first card of the "not seen" part, and then moves a marker. The loop stops when mid reaches hi, because then there are no cards left in the "not seen" part.

Each of the three kinds of card is handled in its own way.

• If the card under mid is a 0, swap it with the card under lo. Then move lo and mid one place to the right. The card that came from lo is always a 1 or a card at the same place, so after the swap the 1 sits at mid, in the ones region. The zero is now before lo, in the zeros region.
• If the card under mid is a 1, it is already in the right region. Move mid one place to the right.
• If the card under mid is a 2, it belongs at the end. Move hi one place to the left, then swap the card under mid with the card under the new hi. The card that moved into mid has not been looked at, so mid stays where it is and the loop checks that card next.

The rule for a 2 is the one that people get wrong. This lesson returns to it in the mistakes section.

Each step makes the "not seen" part one card smaller. A 0 or a 1 moves mid past one card, and a 2 moves hi back past one card. So the loop runs at most as many times as there are cards in the array.

Worked example 1: a six-card row

Start with six values: 2, 0, 2, 1, 0, 1. The program below prints the three markers and the whole array after every step. The lesson's main function, the sort itself, is in the next section. This trace version is the same loop with a print statement added.

#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
 
void show(const vector<int>& a, size_t lo, size_t mid, size_t hi) {
    cout << "  a = ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << "  lo=" << lo << " mid=" << mid << " hi=" << hi << "\n";
}
 
int main() {
    vector<int> a = {2, 0, 2, 1, 0, 1};
    size_t lo = 0;
    size_t mid = 0;
    size_t hi = a.size();
    show(a, lo, mid, hi);
    int step = 0;
    while (mid < hi) {
        ++step;
        if (a[mid] == 0) {
            cout << "step " << step << ": a[mid]=0, swap with lo, move lo and mid\n";
            swap(a[lo], a[mid]);
            ++lo;
            ++mid;
        } else if (a[mid] == 1) {
            cout << "step " << step << ": a[mid]=1, move mid\n";
            ++mid;
        } else {
            cout << "step " << step << ": a[mid]=2, move hi down and swap, mid stays\n";
            --hi;
            swap(a[mid], a[hi]);
        }
        show(a, lo, mid, hi);
    }
}

g++ -std=c++20 -Wall -o trace trace.cpp && ./trace

The output is:

  a = 2 0 2 1 0 1   lo=0 mid=0 hi=6
step 1: a[mid]=2, move hi down and swap, mid stays
  a = 1 0 2 1 0 2   lo=0 mid=0 hi=5
step 2: a[mid]=1, move mid
  a = 1 0 2 1 0 2   lo=0 mid=1 hi=5
step 3: a[mid]=0, swap with lo, move lo and mid
  a = 0 1 2 1 0 2   lo=1 mid=2 hi=5
step 4: a[mid]=2, move hi down and swap, mid stays
  a = 0 1 0 1 2 2   lo=1 mid=2 hi=4
step 5: a[mid]=0, swap with lo, move lo and mid
  a = 0 0 1 1 2 2   lo=2 mid=3 hi=4
step 6: a[mid]=1, move mid
  a = 0 0 1 1 2 2   lo=2 mid=4 hi=4

Read the first step closely. mid is 0 and the card there is a 2. So hi moves from 6 to 5, and the card at index 0 swaps with the card at index 5, which is a 1. The 1 now sits at index 0, and mid stays at 0 so that the 1 is checked. In step 2 it is a 1, so mid moves to 1. Step 3 finds a 0 at mid, which swaps with the card at lo, which is index 0. Now the zero is in the zeros region, and lo and mid both move to 1 and 2.

Look at the last line. mid is 4 and hi is 4, so the "not seen" part is empty and the loop stops. The array is 0 0 1 1 2 2, which is sorted. The loop ran six times, which is the same as the number of cards.

The full function

The sort itself is short. It takes the array by reference, so it changes the caller's vector and does not copy it. Compare it with the trace version above. The only difference is that this one has no printing.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
using namespace std;
 
void sort_flags(vector<int>& a) {
    size_t lo = 0;
    size_t mid = 0;
    size_t hi = a.size();
    while (mid < hi) {
        if (a[mid] == 0) {
            swap(a[lo], a[mid]);
            ++lo;
            ++mid;
        } else if (a[mid] == 1) {
            ++mid;
        } else {
            --hi;
            swap(a[mid], a[hi]);
        }
    }
}
 
void print(const vector<int>& a) {
    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}
 
int main() {
    vector<int> a = {2, 0, 2, 1, 0, 1};
    sort_flags(a);
    print(a);
 
    vector<int> b = {1, 2, 0, 0, 2, 1, 1, 0, 2, 2, 0};
    sort_flags(b);
    print(b);
    cout << "sorted? " << boolalpha << is_sorted(b.begin(), b.end()) << "\n";
 
    mt19937 rng(12345);
    uniform_int_distribution<int> pick(0, 2);
    int failures = 0;
    for (int t = 0; t < 1000; ++t) {
        vector<int> c(static_cast<size_t>(t % 30));
        for (int& x : c) {
            x = pick(rng);
        }
        vector<int> expected = c;
        sort(expected.begin(), expected.end());
        sort_flags(c);
        if (c != expected) {
            ++failures;
        }
    }
    cout << "random cases failed: " << failures << "\n";
}

g++ -std=c++20 -Wall -o flag flag.cpp && ./flag

0 0 1 1 2 2 
0 0 0 0 1 1 1 2 2 2 2 
sorted? true
random cases failed: 0

The first line is the six-card example. The second and third lines are the second example below. The last line is the random test.

The variables lo, mid and hi are all size_t, which is the unsigned index type from the out-of-bounds lesson. Every index is between 0 and a.size(), and hi never goes below mid, so there is no subtraction that could wrap. The loop condition mid < hi is the only test needed. If the vector is empty, hi starts at 0, and the loop does not run.

Worked example 2: eleven cards and a check against a real sort

The second input has eleven values, and the answer is harder to see at a glance: 1, 2, 0, 0, 2, 1, 1, 0, 2, 2, 0. The result is four 0s, three 1s and four 2s. The program prints the sorted list and checks that it is in order with is_sorted.

The output confirms it: 0 0 0 0 1 1 1 2 2 2 2 and sorted? true. Counting the values in the output gives the same totals as the input.

One example is not enough to trust a sort. The main function also runs 1000 test cases on random arrays. For each case it builds a copy, sorts the copy with std::sort, which is the standard library's general sort, and checks that sort_flags gives the same result. The random numbers come from mt19937 with the fixed seed 12345, so every run builds the same 1000 arrays. The arrays have lengths from 0 to 29 and hold only 0, 1 and 2. The count of failed cases is printed, and it is 0.

Using a fixed seed is important for a test. If the seed changed every run, a failure might appear once and then vanish, and you could not repeat it. A fixed seed gives the same inputs every time, so a failure can be reproduced and fixed.

The random test has one blind spot. It only uses 0, 1 and 2, and so does the function. Values outside that range are covered in the common mistakes section.

Worked example 3: the one-line mistake

The bug below looks like a small change. It adds ++mid to the branch for a 2. The rest of the function is the same.

#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
 
void buggy(vector<int>& a) {
    size_t lo = 0;
    size_t mid = 0;
    size_t hi = a.size();
    while (mid < hi) {
        if (a[mid] == 0) {
            swap(a[lo], a[mid]);
            ++lo;
            ++mid;
        } else if (a[mid] == 1) {
            ++mid;
        } else {
            --hi;
            swap(a[mid], a[hi]);
            ++mid;
        }
    }
}
 
int main() {
    vector<int> a = {2, 0, 2, 1, 0, 1};
    buggy(a);
    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}

g++ -std=c++20 -Wall -o bug_mid bug_mid.cpp && ./bug_mid

0 1 0 1 2 2 

The result is wrong. Here is what happened. The input is the same six-card row as before.

1. mid is 0 and the card is a 2. hi moves to 5 and the card at 0 swaps with the 1 at 5. The row is now 1 0 2 1 0 2. The bug then moves mid to 1, so the card at index 0 is never checked again. That card is a 1, which is correct for now.
2. mid is 1 and the card is a 0. It swaps with the card at lo, which is index 0. The row is now 0 1 2 1 0 2, and lo and mid move to 1 and 2.
3. mid is 2 and the card is a 2. hi moves to 4 and the card at 2 swaps with the 0 at index 4. The row is now 0 1 0 1 2 2. The bug moves mid to 3, which skips index 2.

The 0 at index 2 came in from the swap in step 3. The loop never looked at it, because mid jumped over it. The output has a 0 in the middle of the ones, and the program reports no error.

The rule is that a card that comes in from hi has not been checked, so mid must stay where it is. The correct branch for a 2 has only the --hi and the swap. The lesson's first version does exactly that.

Common mistakes

Advancing mid after a 2. This is the bug in worked example 3. The result is a list that looks almost sorted and is not. Test it with a short input such as {1, 2, 0}. The correct output is 0 1 2, but the buggy version prints 1 0 2.

Setting hi to size() - 1. This is a common variant. If hi is the index of the last card, the loop must test mid <= hi, and the unsigned subtraction wraps for an empty vector. The version in this lesson uses hi as the position just past the last card. The loop test is mid < hi, and the subtraction is only done inside the 2 branch, after hi is known to be greater than mid. The lesson's version handles an empty vector without a special case.

Values other than 0, 1 and 2. The function treats any value that is not 0 or 1 as a 2. So a 7 is moved to the end, and the result is not a sorted list of 0, 1 and 2 values in the usual sense. Run this program with the input {1, 7, 0}:

vector<int> odd = {1, 7, 0};
sort_flags(odd);

The output is 0 1 7. The 7 went to the end because the function's else branch takes everything that is not 0 or 1. If your input can hold other values, check the input before sorting, for example with ranges::all_of(a, [](int x) { return x >= 0 && x <= 2; }).

Expecting the method to keep the order of equal items. The swaps can move one 0 past another 0, or one 2 past another 2. For plain numbers this makes no difference, because equal numbers look the same. If each card carries other data, such as a name, the order of cards with the same code can change. For that case use a stable sort, which keeps equal items in their original order.

Mixing up inclusive and exclusive ends. In this lesson, hi is the first position of the twos region, so the "not seen" part is [mid, hi). The end is not included. If you change the meaning of hi in one line but not the others, the loop will read the wrong card or stop too early.

Practice

1. Trace the function by hand on the input {1, 0, 2}. Write the value of lo, mid, hi and the array after each step, then give the final output.

Show the answer

Start with lo 0, mid 0, hi 3, and the array 1 0 2. Step 1: the card at mid is a 1, so mid becomes 1. Step 2: the card at mid is a 0, so swap it with the card at lo, which is 0. The array is 0 1 2, lo becomes 1 and mid becomes 2. Step 3: the card at mid is a 2, so hi becomes 2 and the card at mid swaps with the card at hi. Both are index 2, so nothing changes. Now mid is 2 and hi is 2, so the loop stops. The output is 0 1 2.

2. The input is {2, 2, 2}. What does the function print?

Show the answer

It prints 2 2 2. The card at mid is a 2 each time, so hi goes down by one and the card swaps with the card at the new hi until hi is 0. Then mid is no longer less than hi, and the loop stops. The array was already sorted, and it stays the same.

3. Run the function on an empty vector and on a vector with one value, {1}. What happens?

Show the answer

Both cases work without a special check. The empty vector starts with hi equal to 0, so mid < hi is false and the loop never runs. The one-value vector {1} has mid 0 and hi 1. The card is a 1, so mid becomes 1, the loop stops, and the output is 1. 4. The buggy version in worked example 3 gives 0 1 0 1 2 2. Find the one line to change so that it is correct, and say why that change fixes it.

Show the answer

Remove the ++mid; line from the branch for a 2. Then mid stays where it is after the swap, so the card that came in from hi is checked on the next step. The corrected function gives 0 0 1 1 2 2 for the same input, which is the result the first version gives.

5. Write a loop in main that sorts the values with 2s first, then 1s, then 0s, using the function sort_flags as it is. Hint: map each value x to 2 - x before sorting, then map it back after sorting.

Show the answer

Change each value to 2 - x, call sort_flags, then change each value back with 2 - x again. The map turns 0 into 2, 1 into 1 and 2 into 0. Sorting in ascending order then puts the values that were 2 first, followed by 1s, and the values that were 0 last. Mapping back gives the descending order. Written as a loop, the code is for (int& x : a) x = 2 - x; before the call and the same loop after it. This only works for the values 0, 1 and 2.

Summary

• One pass with three markers sorts 0s, 1s and 2s without counting first.
• The array is always split into zeros, ones, unchecked cards and twos, and each step moves one marker.
• A 2 moves hi down and swaps, and mid stays put, because the card that came in has not been checked.
• The loop runs at most once for each card, since the unchecked part shrinks by one every step.
• The method is not stable. Equal values can change their order when they carry other data.