Задача о голландском флаге (Sort Colors): трёхстороннее разбиение за один проход

Задача о голландском флаге и Sort Colors: три указателя Дейкстры за один проход, инварианты, типичные ошибки, трёхстороннее разбиение в quick sort и сортировка k цветов. Код на Python.

13 мин чтенияалгоритмы · массивы · два указателя · сортировка

Коротко

ВопросОтвет
Что решаемПереставить массив из трёх видов значений так, чтобы шли группы: «меньше», «равно», «больше»
Оптимальное времяO(n)O(n), один проход
ПамятьO(1)O(1), всё на месте
Главная идеяТри указателя low, mid, high делят массив на четыре зоны, неизвестная зона сжимается на 1 за шаг
Где ещё нужнаТрёхстороннее разбиение в quick sort и quickselect, массивы с кучей дубликатов
  • Классическая формулировка на LeetCode — задача 75 Sort Colors: массив из 0, 1 и 2, отсортировать на месте, в follow-up просят один проход.
  • Подсчёт (два прохода) — честное решение, но интервьюер почти всегда попросит однопроходное.
  • Самая частая ошибка — сдвинуть mid после обмена с high.

Откуда взялось название

Задачу сформулировал Эдсгер Дейкстра в книге «A Discipline of Programming» (1976). Флаг Нидерландов — три горизонтальные полосы: красная, белая, синяя. Представьте ряд шариков трёх цветов вперемешку. Нужно переложить их так, чтобы сначала шли все красные, потом белые, потом синие. При этом смотреть на цвет каждого шарика можно один раз, а переставлять — только обменом двух шариков местами.

На собеседованиях вместо цветов обычно дают числа:

вход:  [2, 0, 2, 1, 1, 0]
выход: [0, 0, 1, 1, 2, 2]

Встроенную сортировку использовать нельзя, дополнительный массив тоже. Задача выглядит простой, но в ней спрятан приём, который пригодится в quick sort, quickselect и десятке задач на разбиение массива.

Решение «в лоб»: просто отсортировать

nums.sort() даёт O(nlog⁡n)O(n \log n) и формально решает задачу. Но на собеседовании это засчитают только как отправную точку: значений всего три, и было бы странно платить логарифм за то, что можно сделать линейно.

Решение через подсчёт: два прохода

Раз значений три, их можно просто посчитать, а потом переписать массив заново. Это сортировка подсчётом в самом простом виде.

def sort_colors_counting(nums: list[int]) -> None: cnt = [0, 0, 0] for x in nums: cnt[x] += 1 i = 0 for color in range(3): for _ in range(cnt[color]): nums[i] = color i += 1

Время O(n)O(n), память O(1)O(1). Решение корректное, и его стоит проговорить вслух — оно показывает, что вы видите структуру входа. Но у него два недостатка:

  1. Два прохода по массиву. Follow-up в Sort Colors прямо просит один.
  2. Оно работает только для «голых» чисел. Если сортировать объекты по ключу (заказы по статусу, задачи по приоритету), перезаписать элемент значением color нельзя — исходные объекты потеряются. Нужно именно переставлять элементы.

Второй пункт важнее, чем кажется: в quick sort мы разбиваем массив произвольных значений относительно опорного, и подсчёт там вообще неприменим.

Промежуточный вариант: два разбиения

Можно свести задачу к тому, что уже умеем. Двухстороннее разбиение «подходит / не подходит» — это ровно то, что делается в Move Zeroes и в разбиении Ломуто. Сделаем его дважды: сначала соберём в начало все нули, потом среди оставшихся — все единицы.

def sort_colors_two_pass(nums: list[int]) -> None: def partition(lo: int, pred) -> int: # переносит элементы, для которых pred истинен, в начало nums[lo:] for i in range(lo, len(nums)): if pred(nums[i]): nums[lo], nums[i] = nums[i], nums[lo] lo += 1 return lo border = partition(0, lambda x: x == 0) partition(border, lambda x: x == 1)

Это уже настоящие перестановки, а не перезапись, но проходов по-прежнему два. Чтобы уложиться в один, нужно разбивать сразу на три части.

Алгоритм Дейкстры: три указателя

Инвариант

Заведём три указателя и договоримся, что в любой момент массив устроен так:

 0 .. low-1   low .. mid-1   mid .. high   high+1 .. n-1
[  все 0    |    все 1     |  неизвестно  |    все 2    ]
  • nums[0..low-1] — только нули;
  • nums[low..mid-1] — только единицы;
  • nums[mid..high] — ещё не просмотренные элементы;
  • nums[high+1..n-1] — только двойки.

В начале low = mid = 0, high = n - 1: неизвестная зона — весь массив, остальные три пусты, инвариант выполняется. Цель — сжать неизвестную зону до нуля. Когда mid > high, остаются только зоны нулей, единиц и двоек — массив отсортирован.

Шаг

Смотрим на nums[mid] — первый неизвестный элемент:

  • 0 — ему место в конце зоны нулей. Меняем nums[mid] и nums[low]. На позиции low раньше стояла единица (или, если зона единиц пуста, сам этот ноль), она переезжает на mid — то есть в конец зоны единиц. Сдвигаем low и mid.
  • 1 — он уже стоит на границе зоны единиц. Просто mid += 1.
  • 2 — ему место в начале зоны двоек. Меняем nums[mid] и nums[high], сдвигаем high вниз. А вот mid не трогаем: элемент, который прилетел с позиции high, мы ещё не видели.
def sort_colors(nums: list[int]) -> None: low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: nums[mid], nums[high] = nums[high], nums[mid] high -= 1 a = [2, 0, 2, 1, 1, 0] sort_colors(a) print(a) # [0, 0, 1, 1, 2, 2]

Асимметрия между первой и третьей веткой — ключ ко всей задаче. Слева от mid лежат только уже проверенные элементы, поэтому из позиции low к нам может прийти только единица, и её смотреть заново не нужно. Справа от mid — непроверенные, поэтому элемент с позиции high может оказаться чем угодно, в том числе нулём или двойкой.

Разбор на примере

Прогоним [2, 0, 2, 1, 1, 0]:

low mid high  массив до шага     nums[mid]  действие              массив после
 0   0   5    [2, 0, 2, 1, 1, 0]     2      swap(mid, high), high-- [0, 0, 2, 1, 1, 2]
 0   0   4    [0, 0, 2, 1, 1, 2]     0      swap(low, mid), low++, mid++
 1   1   4    [0, 0, 2, 1, 1, 2]     0      swap(low, mid), low++, mid++
 2   2   4    [0, 0, 2, 1, 1, 2]     2      swap(mid, high), high-- [0, 0, 1, 1, 2, 2]
 2   2   3    [0, 0, 1, 1, 2, 2]     1      mid++
 2   3   3    [0, 0, 1, 1, 2, 2]     1      mid++
 2   4   3    стоп: mid > high

Обратите внимание на первую строку: после обмена на позицию mid пришёл ноль, и на следующем шаге мы его честно обработали. Если бы mid сдвинулся сразу, этот ноль так и остался бы в зоне единиц.

Сложность

На каждой итерации либо mid растёт, либо high уменьшается — расстояние high - mid сокращается ровно на единицу. Значит, итераций ровно nn, время O(n)O(n). Каждый элемент читается один раз как «неизвестный», обменов не больше nn. Память — три переменные, O(1)O(1).

Про «один проход» есть тонкость: элементы, которые прилетели с конца, мы тоже смотрим один раз, просто позже. Поэтому корректнее говорить «каждый элемент классифицируется ровно один раз», а не «указатель проходит массив один раз».

То же на JavaScript

function sortColors(nums) { let low = 0, mid = 0, high = nums.length - 1 while (mid <= high) { if (nums[mid] === 0) { ;[nums[low], nums[mid]] = [nums[mid], nums[low]] low++ mid++ } else if (nums[mid] === 1) { mid++ } else { ;[nums[mid], nums[high]] = [nums[high], nums[mid]] high-- } } } const a = [2, 0, 2, 1, 1, 0] sortColors(a) console.log(a) // [ 0, 0, 1, 1, 2, 2 ]

Типичные ошибки

mid += 1 после обмена с high. Самый частый баг. На входе [1, 2, 0] такой код вернёт [1, 0, 2]: ноль приехал с конца на позицию mid, а указатель уже ушёл дальше. Запомните правило: двигаем mid только тогда, когда точно знаем, что лежит на его месте.

while mid < high вместо <=. Неизвестная зона nums[mid..high] включает обе границы, поэтому при mid == high в ней ещё один элемент. С условием < массив [1, 0] останется как есть: цикл не выполнится ни разу.

Не сдвинуть mid вместе с low. Тогда после обмена mid может оказаться левее low, и инвариант «зона единиц — low..mid-1» сломается. Код ещё и зациклится на нулях не хуже, чем на двойках.

Ожидать стабильности. Алгоритм не сохраняет исходный порядок равных элементов: обмен с high перебрасывает элементы через весь массив. Если сортируете объекты по ключу и порядок внутри группы важен (как в LeetCode 2161 Partition Array According to Given Pivot), нужен другой подход — например, три списка и склейка, за O(n)O(n) памяти.

Проверять на одном примере. Для таких задач полезна привычка прогнать случайный тест против sorted: десяток строк, зато ловит все ошибки с границами.

import random for _ in range(1000): a = [random.randint(0, 2) for _ in range(random.randint(0, 30))] b = a[:] sort_colors(b) assert b == sorted(a), a print('ok')

Обобщение: разбиение относительно опорного

Вся логика выше не зависит от того, что значения — это 0, 1 и 2. Достаточно уметь сравнивать с опорным значением pivot: «меньше» идёт в левую зону, «равно» — в среднюю, «больше» — в правую.

def three_way_partition(a: list, lo: int, hi: int, pivot) -> tuple[int, int]: """Переставляет a[lo..hi] в < pivot | == pivot | > pivot. Возвращает (lt, gt): a[lt..gt] — блок равных pivot.""" lt, i, gt = lo, lo, hi while i <= gt: if a[i] < pivot: a[lt], a[i] = a[i], a[lt] lt += 1 i += 1 elif a[i] > pivot: a[i], a[gt] = a[gt], a[i] gt -= 1 else: i += 1 return lt, gt a = [5, 1, 5, 9, 3, 5, 7] print(three_way_partition(a, 0, len(a) - 1, 5), a) # (2, 4) [1, 3, 5, 5, 5, 7, 9]

Здесь lt, i, gt — те же low, mid, high, только под именами из учебника Седжвика. Функция возвращает границы средней зоны, и это главное, что нужно от разбиения в быстрой сортировке.

Трёхсторонний quick sort

Классическая быстрая сортировка делит массив на две части: «не больше опорного» и «не меньше». На массиве, где все элементы равны, разбиение Ломуто каждый раз отщепляет по одному элементу, и сортировка деградирует до O(n2)O(n^2). Хоара справляется лучше, но всё равно гоняет равные элементы по рекурсии.

Трёхстороннее разбиение решает проблему радикально: все элементы, равные опорному, сразу встают на свои окончательные места, и в рекурсию уходят только строго меньшие и строго большие.

import random def quicksort_3way(a: list, lo: int = 0, hi: int | None = None) -> None: if hi is None: hi = len(a) - 1 while lo < hi: pivot = a[random.randint(lo, hi)] lt, gt = three_way_partition(a, lo, hi, pivot) # рекурсия в меньшую часть, цикл по большей — стек O(log n) if lt - lo < hi - gt: quicksort_3way(a, lo, lt - 1) lo = gt + 1 else: quicksort_3way(a, gt + 1, hi) hi = lt - 1 a = [3, 5, 2, 5, 3, 1, 5, 2, 3] quicksort_3way(a) print(a) # [1, 2, 2, 3, 3, 3, 5, 5, 5] big = [5] * 200_000 quicksort_3way(big) # одно разбиение — и готово

Что это даёт:

  • Массив из одинаковых элементов сортируется за один проход разбиения: средняя зона — весь массив, рекурсии нет.
  • Если различных значений kk, ожидаемое время — O(nlog⁡k)O(n \log k) вместо O(nlog⁡n)O(n \log n). Для данных вроде «статус заказа» или «оценка от 1 до 5» это почти линейно.
  • Рекурсия в меньшую половину и цикл по большей ограничивают глубину стека O(log⁡n)O(\log n) даже в неудачных случаях. На Python без этого на больших массивах легко упереться в лимит рекурсии.

Цена — чуть больше обменов на массивах без повторов. Поэтому в продакшен-библиотеках используют более хитрые варианты: схема Бентли — Макилроя собирает равные элементы по краям и переносит в середину в конце, а dual-pivot quicksort в Java делит массив на три части двумя опорными. Но на собеседовании ожидают именно схему Дейкстры, и её достаточно.

Тот же приём работает в quickselect: если kk-я позиция попала в отрезок [lt, gt], ответ найден сразу, без лишних шагов на дубликатах. Сравнение quick sort с другими сортировками — в обзоре алгоритмов сортировки.

Больше трёх цветов: Sort Colors II

Задача Sort Colors II (на LintCode это номер 143): в массиве цвета от 1 до kk, отсортировать на месте. Подсчёт снова даёт O(n+k)O(n + k) времени, но O(k)O(k) памяти. Если память ограничена, можно взять идею быстрой сортировки, но делить не массив по значению, а диапазон цветов пополам:

def sort_k_colors(nums: list[int], k: int) -> None: """Цвета 1..k. Делим диапазон цветов пополам: O(n log k), O(log k) памяти.""" def rec(lo: int, hi: int, c_lo: int, c_hi: int) -> None: if lo >= hi or c_lo >= c_hi: return c_mid = (c_lo + c_hi) // 2 i, j = lo, hi while i <= j: if nums[i] <= c_mid: i += 1 else: nums[i], nums[j] = nums[j], nums[i] j -= 1 rec(lo, j, c_lo, c_mid) rec(i, hi, c_mid + 1, c_hi) rec(0, len(nums) - 1, 1, k) a = [3, 2, 2, 1, 4] sort_k_colors(a, 4) print(a) # [1, 2, 2, 3, 4]

На каждом уровне рекурсии каждый элемент участвует в одном разбиении, уровней log⁡k\log k, итого O(nlog⁡k)O(n \log k). При k=3k = 3 это та же задача о флаге, только решённая двумя двухсторонними разбиениями вместо одного трёхстороннего.

Где встречается

Сам Sort Colors — частая задача уровня medium на скринингах: короткая, но сразу видно, умеет ли кандидат держать инвариант и аккуратно работать с границами. Похожие задачи, где работает тот же приём:

  • Move Zeroes и Sort Array By Parity — двухсторонние разбиения, «младшие братья» флага. Удобно начинать с них, а приём с двумя указателями потом расширить до трёх.
  • Wiggle Sort II — найти медиану через quickselect, затем трёхстороннее разбиение относительно неё с хитрой «виртуальной» индексацией, чтобы разложить элементы через один.
  • Partition Array According to Given Pivot — то же разбиение на три группы, но со стабильностью, поэтому решение Дейкстры не подходит.
  • Любая задача «раздели массив по признаку на три группы на месте»: отрицательные, нули, положительные; меньше a, внутри [a, b], больше b.

Как рассказывать на собеседовании

  1. Назвать подсчёт как базовое решение за O(n)O(n) и два прохода.
  2. Сказать, что значений три, поэтому массив можно разбить на зоны, и нарисовать схему с четырьмя зонами.
  3. Проговорить инвариант и три случая. Отдельно объяснить, почему после обмена с high указатель mid не двигается.
  4. Обосновать сложность: high - mid уменьшается на 1 за шаг.
  5. Прогнать короткий пример, например [2, 0, 1], и граничные случаи: пустой массив, все элементы одинаковые.

Если после этого спросят «а где ещё это применяется» — это приглашение рассказать про трёхсторонний quick sort и массивы с дубликатами.

Итого

Задача о голландском флаге учит одному из самых полезных приёмов работы с массивом: держать несколько зон с чётким инвариантом и сжимать неизвестную зону на единицу за шаг. Три указателя, три случая, одна асимметрия — указатель mid стоит на месте после обмена с концом. Поймёте, почему это так, — и трёхстороннее разбиение в quick sort, quickselect и задачах на группировку будет писаться без подглядываний.

Потренироваться в спокойной обстановке

Все задачи