Задача флага Нидерладндов

Задача флага Нидерладндов (англ. Dutch national flag problem, DNF) — задача дискретной математики, которую предложил Эдсгер Дейкстра. Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.

Сортировка набора, состоящего из 0 и 1

Задача:

Дан массив [math]a[1..n][/math] из [math]n[/math] чисел [math]0[/math] и [math]1[/math]. Требуется разделить элементы друг от друга так, чтобы сначала оказались все [math]0[/math], а в конце [math]1[/math].

Пример

Input = [math] [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] [/math]
Output = [math] [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] [/math]

Алгоритм

Будем поддерживать два указателя. Инициализируем первый индекс [math]left = 1[/math] и второй индекс [math]right = n[/math].

У будем делать следующее пока [math]left \lt right[/math]

1. Увеличиваем [math]left[/math] на [math]1[/math] пока не [math]a[left] = 0[/math];
2. Уменьшаем [math]right[/math] на [math]1[/math] пока не [math]a[right] = 1[/math];
3. Если [math]left \lt right[/math], то меняем местами [math]a[left][/math] и [math]a[right][/math], [math]left\texttt{++}[/math], [math]right\texttt{--}[/math].

Псевдокод

int left = 1, right = n;
while (left < right)
    while (arr[left] == 0 and left < right)
        left++
    while (arr[right] == 1 and left < right)
        right-–
    if (left < right)
        swap(a[left], a[right])
        left++
        right–-

Сортировка набора, состоящего из 0, 1 и 2

Задача:

Дан массив [math]a[1..n][/math] из [math]n[/math] чисел [math]0[/math], [math]1[/math] и [math]2[/math]. Требуется разделить их друг от друга так, чтобы сначала шли все [math]0[/math], потом все [math]1[/math] и все [math]2[/math] в конце.

Пример

Input = [math] [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] [/math]
Output = [math] [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] [/math]

Алгоритм

Будем поддерживать три указателя. Инициализация: [math]lo = 1; mid = 1; hi = n;[/math].

У будем делать следующее пока [math]mid \leqslant right[/math]

1. Если [math]a[mid] = 0[/math], то меняем местами [math]a[lo][/math] и [math]a[mid][/math], [math]lo\texttt{++}[/math], [math]mid\texttt{++}[/math];
2. Если [math]a[mid] = 1[/math], то [math]mid\texttt{++}[/math];
3. Если [math]a[mid] = 0[/math], то меняем местами [math]a[mid][/math] и [math]a[hi][/math], [math]hi\texttt{--}[/math];

Инвариант работы алгоритма:

1. [math]a[1..lo-1] = 0[/math]
2. [math]a[lo..mid-1] = 1[/math]
3. [math]a[mid..hi][/math] неизвестны
4. [math]a[hi+1..n] = 2[/math]

Псевдокод

int lo = 1, mid = 1, hi = n;
while mid [math]\leqslant[/math] right
    switch (a[mid])
    case 0:
        swap(a[lo++], a[mid++])
        break
    case 1:
        mid++
        break
    case 2:
        swap(a[mid], a[hi--])
        break

См. также

• Сортировка подсчетом
• Цифровая сортировка

Источники информации

• Wikipedia — Dutch national flag problem
• GeeksforGeeks — Segregate 0s and 1s in an array
• GeeksforGeeks — Sort an array of 0s, 1s and 2s