Задача о голландском флаге (Sort Colors): трёхстороннее разбиение за один проход
Задача о голландском флаге и Sort Colors: три указателя Дейкстры за один проход, инварианты, типичные ошибки, трёхстороннее разбиение в quick sort и сортировка k цветов. Код на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Что решаем | Переставить массив из трёх видов значений так, чтобы шли группы: «меньше», «равно», «больше» |
| Оптимальное время | , один проход |
| Память | , всё на месте |
| Главная идея | Три указателя 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() даёт и формально решает задачу. Но на собеседовании это засчитают только как отправную точку: значений всего три, и было бы странно платить логарифм за то, что можно сделать линейно.
Решение через подсчёт: два прохода
Раз значений три, их можно просто посчитать, а потом переписать массив заново. Это сортировка подсчётом в самом простом виде.
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
Время , память . Решение корректное, и его стоит проговорить вслух — оно показывает, что вы видите структуру входа. Но у него два недостатка:
- Два прохода по массиву. Follow-up в Sort Colors прямо просит один.
- Оно работает только для «голых» чисел. Если сортировать объекты по ключу (заказы по статусу, задачи по приоритету), перезаписать элемент значением
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 сокращается ровно на единицу. Значит, итераций ровно , время . Каждый элемент читается один раз как «неизвестный», обменов не больше . Память — три переменные, .
Про «один проход» есть тонкость: элементы, которые прилетели с конца, мы тоже смотрим один раз, просто позже. Поэтому корректнее говорить «каждый элемент классифицируется ровно один раз», а не «указатель проходит массив один раз».
То же на 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), нужен другой подход — например, три списка и склейка, за памяти.
Проверять на одном примере. Для таких задач полезна привычка прогнать случайный тест против 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
Классическая быстрая сортировка делит массив на две части: «не больше опорного» и «не меньше». На массиве, где все элементы равны, разбиение Ломуто каждый раз отщепляет по одному элементу, и сортировка деградирует до . Хоара справляется лучше, но всё равно гоняет равные элементы по рекурсии.
Трёхстороннее разбиение решает проблему радикально: все элементы, равные опорному, сразу встают на свои окончательные места, и в рекурсию уходят только строго меньшие и строго большие.
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) # одно разбиение — и готово
Что это даёт:
- Массив из одинаковых элементов сортируется за один проход разбиения: средняя зона — весь массив, рекурсии нет.
- Если различных значений , ожидаемое время — вместо . Для данных вроде «статус заказа» или «оценка от 1 до 5» это почти линейно.
- Рекурсия в меньшую половину и цикл по большей ограничивают глубину стека даже в неудачных случаях. На Python без этого на больших массивах легко упереться в лимит рекурсии.
Цена — чуть больше обменов на массивах без повторов. Поэтому в продакшен-библиотеках используют более хитрые варианты: схема Бентли — Макилроя собирает равные элементы по краям и переносит в середину в конце, а dual-pivot quicksort в Java делит массив на три части двумя опорными. Но на собеседовании ожидают именно схему Дейкстры, и её достаточно.
Тот же приём работает в quickselect: если -я позиция попала в отрезок [lt, gt], ответ найден сразу, без лишних шагов на дубликатах. Сравнение quick sort с другими сортировками — в обзоре алгоритмов сортировки.
Больше трёх цветов: Sort Colors II
Задача Sort Colors II (на LintCode это номер 143): в массиве цвета от 1 до , отсортировать на месте. Подсчёт снова даёт времени, но памяти. Если память ограничена, можно взять идею быстрой сортировки, но делить не массив по значению, а диапазон цветов пополам:
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]
На каждом уровне рекурсии каждый элемент участвует в одном разбиении, уровней , итого . При это та же задача о флаге, только решённая двумя двухсторонними разбиениями вместо одного трёхстороннего.
Где встречается
Сам Sort Colors — частая задача уровня medium на скринингах: короткая, но сразу видно, умеет ли кандидат держать инвариант и аккуратно работать с границами. Похожие задачи, где работает тот же приём:
- Move Zeroes и Sort Array By Parity — двухсторонние разбиения, «младшие братья» флага. Удобно начинать с них, а приём с двумя указателями потом расширить до трёх.
- Wiggle Sort II — найти медиану через quickselect, затем трёхстороннее разбиение относительно неё с хитрой «виртуальной» индексацией, чтобы разложить элементы через один.
- Partition Array According to Given Pivot — то же разбиение на три группы, но со стабильностью, поэтому решение Дейкстры не подходит.
- Любая задача «раздели массив по признаку на три группы на месте»: отрицательные, нули, положительные; меньше
a, внутри[a, b], большеb.
Как рассказывать на собеседовании
- Назвать подсчёт как базовое решение за и два прохода.
- Сказать, что значений три, поэтому массив можно разбить на зоны, и нарисовать схему с четырьмя зонами.
- Проговорить инвариант и три случая. Отдельно объяснить, почему после обмена с
highуказательmidне двигается. - Обосновать сложность:
high - midуменьшается на 1 за шаг. - Прогнать короткий пример, например
[2, 0, 1], и граничные случаи: пустой массив, все элементы одинаковые.
Если после этого спросят «а где ещё это применяется» — это приглашение рассказать про трёхсторонний quick sort и массивы с дубликатами.
Итого
Задача о голландском флаге учит одному из самых полезных приёмов работы с массивом: держать несколько зон с чётким инвариантом и сжимать неизвестную зону на единицу за шаг. Три указателя, три случая, одна асимметрия — указатель mid стоит на месте после обмена с концом. Поймёте, почему это так, — и трёхстороннее разбиение в quick sort, quickselect и задачах на группировку будет писаться без подглядываний.