Блочная сортировка (Bucket Sort): идея, код и задачи на бакеты
Bucket sort простыми словами: как раскладывать числа по корзинам, когда сортировка работает за O(n), чем отличается от counting sort и radix sort, плюс Maximum Gap и Top K Frequent.
Коротко
| Параметр | Значение |
|---|---|
| Средняя сложность | O(n + m), где m — число бакетов; при m ≈ n и равномерных данных — O(n) |
| Худший случай | O(n²) с сортировкой вставками внутри бакета, O(n log n) — с встроенной сортировкой |
| Дополнительная память | O(n + m) |
| Устойчивая | да, если устойчива сортировка внутри бакетов |
| Главное условие | данные распределены по диапазону примерно равномерно |
Идея в одну строку: разбей диапазон значений на равные корзины, разложи числа по корзинам, отсортируй каждую корзину и склей их по порядку. А на собеседованиях бакеты чаще встречаются не как сортировка, а как приём: Maximum Gap, Top K Frequent, поиск почти-дубликатов в окне.
Идея: сначала грубо, потом точно
Представьте, что надо разложить по алфавиту тысячу бумажных анкет. Никто не станет сравнивать их попарно. Сначала раскладываете по стопкам «А–В», «Г–Е», «Ж–И» и так далее, потом сортируете каждую маленькую стопку и складываете стопки по порядку.
Это и есть блочная (карманная, корзинная) сортировка, bucket sort. В ней два уровня:
- Грубое разбиение без сравнений. По значению элемента сразу вычисляем номер бакета. Для числа
xиз[0, 1)иnбакетов этоint(x * n). Никаких сравнений, одна арифметическая операция. - Точная сортировка внутри бакета. Бакеты маленькие, поэтому сортируются быстро любым способом, хоть вставками.
Ключевое свойство: если бакет i левее бакета j, то любой элемент из i не больше любого элемента из j. Поэтому после сортировки бакетов достаточно просто приклеить их друг к другу.
Разбор на примере
Возьмём классический пример из учебника Кормена: 10 чисел из [0, 1).
[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
Бакетов тоже 10, номер бакета int(x * 10) — по сути, первая цифра после запятой:
бакет 0: —
бакет 1: 0.17, 0.12
бакет 2: 0.26, 0.21, 0.23
бакет 3: 0.39
бакет 4: —
бакет 5: —
бакет 6: 0.68
бакет 7: 0.78, 0.72
бакет 8: —
бакет 9: 0.94
Сортируем каждый бакет:
бакет 1: 0.12, 0.17
бакет 2: 0.21, 0.23, 0.26
бакет 7: 0.72, 0.78
Склеиваем слева направо:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
Самый большой бакет — из трёх элементов. Сортировать три числа почти бесплатно, а сложение бакетов — один линейный проход.
Реализация на Python
Базовая версия для чисел из [0, 1)
def bucket_sort(arr: list[float]) -> list[float]: """Сортирует числа из полуинтервала [0, 1).""" n = len(arr) if n <= 1: return arr[:] buckets = [[] for _ in range(n)] for x in arr: buckets[int(x * n)].append(x) # x из [0, 1) -> индекс 0..n-1 result = [] for b in buckets: b.sort() # бакеты маленькие, сортировка дешёвая result.extend(b) return result print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68])) # [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
Важно, что интервал полуоткрытый: число 1.0 дало бы индекс n и IndexError.
Версия для произвольного диапазона
На практике числа редко лежат в [0, 1). Нормируем их по min и max: ширина бакета (max − min) / m, номер бакета (x − min) / width.
def bucket_sort_range(arr: list[float], bucket_count: int | None = None) -> list[float]: """Сортирует произвольные числа: бакеты строятся по диапазону [min, max].""" n = len(arr) if n <= 1: return arr[:] lo, hi = min(arr), max(arr) if lo == hi: return arr[:] # все элементы равны, делить на ноль не будем m = bucket_count or n width = (hi - lo) / m buckets = [[] for _ in range(m)] for x in arr: i = min(int((x - lo) / width), m - 1) # max попадает ровно на правую границу buckets[i].append(x) result = [] for b in buckets: result.extend(sorted(b)) return result print(bucket_sort_range([29, -3, 7.5, 14, 0, 29, 3])) # [-3, 0, 3, 7.5, 14, 29, 29]
Две детали, на которых спотыкаются чаще всего:
- Максимум. Для
x == maxвыражение(x − min) / widthравно ровноm, а такого бакета нет. Отсюдаmin(..., m - 1). Заодно он страхует от погрешностей деления с плавающей точкой. - Все элементы равны. Тогда
width = 0и деление на ноль. Отдельная проверкаlo == hi.
Внутренняя сортировка вставками
Классическое описание bucket sort использует внутри бакета сортировку вставками: на крошечных массивах она быстрее «умных» алгоритмов, к тому же устойчива. В Python встроенный sorted (Timsort) на маленьких кусках и так переходит на вставки, поэтому руками писать незачем. Но на собеседовании могут попросить, и тогда:
def insertion_sort(a: list[float]) -> None: for i in range(1, len(a)): x = a[i] j = i - 1 while j >= 0 and a[j] > x: a[j + 1] = a[j] j -= 1 a[j + 1] = x
Строгое a[j] > x сохраняет порядок равных элементов, а значит, вся сортировка остаётся устойчивой.
Когда bucket sort действительно работает за O(n)
Тут важно не сказать на собеседовании «bucket sort — это O(n)» без оговорок. Линейное время у него ожидаемое и только при условии на данные.
Что считаем
Пусть n элементов и m бакетов, в бакет i попало элементов. Тогда работа:
- раскладка — O(n);
- создание и обход бакетов — O(m);
- сортировка вставками внутри — .
Первые два слагаемых всегда линейны. Вся интрига — в сумме квадратов.
Равномерное распределение
Если элементы независимы и равномерно распределены по диапазону, каждый попадает в бакет i с вероятностью . При m = n у Кормена показано, что
то есть математическое ожидание квадрата размера бакета — константа, меньше 2. Тогда ожидаемая суммарная работа внутри бакетов , и весь алгоритм — O(n) в среднем.
Интуиция: в среднем в бакете один элемент. Бывают бакеты на 2–3 элемента, бывают пустые, но «тяжёлые» бакеты на десятки элементов при равномерных данных крайне редки.
Строго говоря, достаточно даже более слабого условия: чтобы сумма квадратов размеров бакетов была линейной. Равномерность — самый частый способ это гарантировать.
Когда всё ломается
Возьмите данные с сильным перекосом: 999 чисел в районе 0.5 и одно число 1000. Диапазон [0.5, 1000] делится на 1000 бакетов шириной около единицы, и все 999 чисел падают в бакет 0. Получили одну сортировку на 999 элементов, а бакеты потрачены впустую.
| Данные | Что происходит | Время |
|---|---|---|
| равномерные, m ≈ n | в каждом бакете O(1) элементов | O(n) в среднем |
| сильно скошенные, выбросы | почти всё в одном бакете | O(n²) со вставками, O(n log n) с sorted |
| мало различных значений, много повторов | повторы всегда в одном бакете | зависит от внутренней сортировки |
Поэтому в реальных реализациях внутри бакета часто ставят сортировку с гарантией O(k log k): худший случай тогда не хуже обычной сортировки сравнением.
Почему это не нарушает нижнюю оценку
Любая сортировка сравнениями требует в худшем случае. Bucket sort её не нарушает по двум причинам: раскладка по бакетам — не сравнение, а вычисление по значению, и линейность обещана только в среднем на «хороших» данных. Подробнее про эту оценку — в статье про нотацию Big O и в сравнении сортировок.
Сравнение с counting sort и radix sort
Все три — сортировки «без сравнений», и их постоянно путают. По сути, это родственники.
| Counting sort | Bucket sort | Radix sort | |
|---|---|---|---|
| Что раскладываем | каждое значение — в свою ячейку | диапазон значений — в бакеты | по одной цифре за проход |
| Ширина «корзины» | ровно одно значение | (max − min) / m | одна цифра в основании b |
| Данные | целые из небольшого диапазона k | числа, в том числе дробные, желательно равномерные | целые или строки фиксированной длины |
| Время | O(n + k) всегда | O(n) в среднем, хуже при перекосе | O(d · (n + b)) всегда |
| Память | O(k) | O(n + m) | O(n + b) |
| Сортировка внутри | не нужна | нужна | не нужна, но каждый проход обязан быть устойчивым |
| Зависимость от распределения | нет | сильная | нет |
Полезно видеть связи:
- Counting sort — это bucket sort, где каждый бакет шириной в одно значение. Внутри бакета все элементы равны, поэтому сортировать их не нужно. Цена — массив размера k на весь диапазон.
- Radix sort — это много проходов bucket sort с 10 (или 256) бакетами по одной цифре. MSD-вариант radix sort буквально раскладывает по старшей цифре и рекурсивно сортирует каждый бакет.
- Bucket sort — компромисс. Бакетов столько, сколько элементов, а не значений, поэтому огромный диапазон не страшен. Зато платим зависимостью от распределения.
Что выбрать:
- целые из узкого диапазона (оценки, возрасты, буквы) — counting sort;
- длинные целые ключи (32/64-битные id, телефоны) — radix sort;
- дробные числа, про которые известно, что они примерно равномерны (вероятности, случайные значения, хеши) — bucket sort;
- ничего не знаете про данные — обычный
sorted, не выдумывайте.
Где bucket sort встречается в жизни
Как самостоятельная сортировка — нечасто: Timsort и introsort в стандартных библиотеках закрывают почти всё. А вот идея «разбить по диапазонам, а потом разбираться внутри» живёт повсюду:
- Гистограммы и перцентили. Метрики латентности (Prometheus histograms, HDR Histogram) хранят не все значения, а счётчики по бакетам.
- Внешняя сортировка и шардирование по диапазонам. Разбиваем данные по ключу на диапазоны, каждый сортируем отдельно, на своей машине или в своём файле. Это bucket sort в масштабе кластера; подробнее про шарды — в статье про шардирование и репликацию.
- Пространственные сетки. Чтобы найти близкие точки на карте, их раскладывают по клеткам сетки: соседи могут быть только в своей или в соседней клетке. Этот же приём ниже решит задачу про почти-дубликаты.
Задача: Maximum Gap
Самая известная задача на бакеты (LeetCode 164, Hard).
Дан массив целых неотрицательных чисел. Найдите максимальную разность между соседними элементами в отсортированном виде массива. Если элементов меньше двух — верните 0. Решение должно работать за O(n) времени и памяти.
Пример: [3, 6, 9, 1] → в отсортированном виде [1, 3, 6, 9], разности 2, 3, 3 → ответ 3.
Наивное решение
Отсортировать и пройтись по соседям: O(n log n). Работает, но условие прямо требует линейного времени. Можно сделать radix sort — это честный O(n) для ограниченных целых. Но есть более изящный путь.
Ключевое наблюдение: ответ не может быть маленьким
Пусть lo и hi — минимум и максимум, всего n чисел, значит, n − 1 промежуток между соседями. Сумма этих промежутков равна hi − lo. Если бы все промежутки были меньше , их сумма была бы меньше hi − lo. Противоречие. Значит:
Теперь возьмём бакеты шириной не больше этой величины. Два числа внутри одного бакета отличаются меньше чем на ширину бакета, значит, максимальный промежуток никогда не лежит внутри бакета. Он всегда между бакетами: от максимума одного непустого бакета до минимума следующего непустого.
Отсюда алгоритм: сортировать содержимое бакетов не нужно вообще. Достаточно хранить для каждого бакета только min и max.
Решение за O(n)
def maximum_gap(nums: list[int]) -> int: n = len(nums) if n < 2: return 0 lo, hi = min(nums), max(nums) if lo == hi: return 0 size = max(1, (hi - lo) // (n - 1)) # ширина бакета не больше минимально возможного ответа count = (hi - lo) // size + 1 mins = [None] * count maxs = [None] * count for x in nums: i = (x - lo) // size if mins[i] is None: mins[i] = maxs[i] = x else: mins[i] = min(mins[i], x) maxs[i] = max(maxs[i], x) best = 0 prev_max = lo for i in range(count): if mins[i] is None: continue # пустой бакет пропускаем best = max(best, mins[i] - prev_max) prev_max = maxs[i] return best print(maximum_gap([3, 6, 9, 1])) # 3 print(maximum_gap([10])) # 0 print(maximum_gap([1, 10000000])) # 9999999
Разберём [3, 6, 9, 1]: lo = 1, hi = 9, n = 4, ширина size = 8 // 3 = 2, бакетов 8 // 2 + 1 = 5.
бакет 0 [1, 2]: 1 → min 1, max 1
бакет 1 [3, 4]: 3 → min 3, max 3
бакет 2 [5, 6]: 6 → min 6, max 6
бакет 3 [7, 8]: —
бакет 4 [9, 10]: 9 → min 9, max 9
Промежутки между соседними непустыми бакетами: 3 − 1 = 2, 6 − 3 = 3, 9 − 6 = 3. Ответ 3.
Почему ширина берётся округлением вниз, а не вверх? Ширина должна быть не больше нижней оценки ответа, чтобы внутри бакета разности были строго меньше ответа. Округление вниз это гарантирует, а max(1, ...) спасает от нулевой ширины, когда чисел больше, чем диапазон.
Сложность: O(n) по времени и O(n) по памяти: при ширине ⌊(hi − lo) / (n − 1)⌋ бакетов получается меньше 2n. Метод работает и для отрицательных чисел: всё считается от lo.
Это хорошая задача на собеседовании именно потому, что проверяет понимание, а не заученный шаблон: нужно доказать, что ответ лежит между бакетами.
Задача: Top K Frequent Elements
Задача «Самые часто встречающиеся элементы» (LeetCode 347, Medium): вернуть k самых частых элементов массива. Стандартное решение через кучу даёт O(n log k). Бакеты дают O(n).
Наблюдение: частота любого элемента — целое число от 1 до n. Значит, можно завести n + 1 бакет, где buckets[c] — список чисел, встретившихся ровно c раз. Это bucket sort по частоте, а точнее, counting sort: каждая частота — свой бакет, сортировать внутри не нужно.
from collections import Counter def top_k_frequent(nums: list[int], k: int) -> list[int]: freq = Counter(nums) # buckets[c] — числа, которые встретились ровно c раз; c от 1 до n buckets = [[] for _ in range(len(nums) + 1)] for num, c in freq.items(): buckets[c].append(num) result = [] for c in range(len(buckets) - 1, 0, -1): # от самых частых к редким for num in buckets[c]: result.append(num) if len(result) == k: return result return result print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # [1, 2] print(top_k_frequent([1], 1)) # [1]
Подсчёт частот — O(n) через хеш-таблицу, раскладка — O(число различных элементов), обход бакетов с конца — O(n). Итого O(n) времени и памяти.
Когда какое решение предлагать:
| Подход | Время | Память | Когда хорош |
|---|---|---|---|
| сортировка по частоте | O(n log n) | O(n) | для старта и проверки |
| куча размера k | O(n log k) | O(n + k) | k много меньше n, поток данных |
| бакеты по частоте | O(n) | O(n) | весь массив в памяти, нужна асимптотика |
| quickselect | O(n) в среднем | O(n) | альтернатива без лишнего массива |
Тот же приём работает в задаче «отсортировать символы строки по частоте» (LeetCode 451): частота ограничена длиной строки, значит, бакеты.
Бонус: почти-дубликаты в окне
У задачи «Дубликаты на расстоянии» (LeetCode 219) есть усложнённая версия, LeetCode 220 «Contains Duplicate III»: найти два индекса i ≠ j, такие что |i − j| ≤ k и |nums[i] − nums[j]| ≤ t. Её часто дают как follow-up.
Решение через бакеты шириной t + 1:
- два числа в одном бакете отличаются не больше чем на t — сразу ответ
True; - близкое число может оказаться ещё в соседнем бакете — проверяем его отдельно;
- в дальних бакетах близких чисел быть не может.
Держим в словаре только элементы из скользящего окна последних k индексов. В каждом бакете не больше одного элемента: если бы появился второй, мы бы уже вернули True.
def contains_nearby_almost_duplicate(nums: list[int], k: int, t: int) -> bool: if t < 0 or k <= 0: return False w = t + 1 # в одном бакете любые два числа отличаются не больше чем на t buckets = {} # id бакета -> число из окна последних k элементов for i, x in enumerate(nums): b = x // w # // корректно округляет вниз и для отрицательных if b in buckets: return True if b - 1 in buckets and x - buckets[b - 1] <= t: return True if b + 1 in buckets and buckets[b + 1] - x <= t: return True buckets[b] = x if i >= k: del buckets[nums[i - k] // w] # элемент выпал из окна return False print(contains_nearby_almost_duplicate([1, 2, 3, 1], 3, 0)) # True print(contains_nearby_almost_duplicate([1, 5, 9, 1, 5, 9], 2, 3)) # False
Время O(n), память O(min(n, k)). Альтернатива — упорядоченное множество в окне за O(n log k), но в Python его нет из коробки, и бакеты здесь проще.
Обратите внимание на x // w: в Python целочисленное деление округляет вниз, поэтому -1 // 3 == -1, а не 0. В Java и C++ деление округляет к нулю, и там отрицательные числа надо обрабатывать отдельно, иначе −1 и 1 окажутся в одном бакете.
Типичные ошибки
- Говорить «bucket sort — O(n)» без оговорок. Правильно: O(n) в среднем при равномерном распределении, O(n²) в худшем случае со вставками внутри.
- Выход за границы бакетов. Для
x == maxиндекс получается ровноm. Нужноmin(i, m - 1)илиm + 1бакет. - Деление на ноль при
min == max. Проверка на одинаковые элементы обязательна, это частый граничный тест. - Отрицательные числа. Формула
int(x * n)рассчитана на[0, 1). Для общего случая нормируйте черезx − min. В языках с делением к нулю следите за знаком. - Неустойчивая сортировка внутри бакетов. Если нужна устойчивость (например, сортировка записей по ключу), внутренняя сортировка тоже должна быть устойчивой.
- Слишком мало или слишком много бакетов. Мало — бакеты распухают, и выигрыша нет. Много — время уходит на создание и обход пустых. Начальный ориентир — m ≈ n.
- В Maximum Gap — сортировать бакеты. Это лишняя работа и потеря линейности. Достаточно min и max каждого бакета.
Что спрашивают на собеседованиях
- «Почему bucket sort может быть быстрее O(n log n)?» Раскладка по бакетам вычисляется по значению, а не через сравнения, и линейность получается в среднем при равномерных данных.
- «Какой худший случай и как его улучшить?» Все элементы в одном бакете. Улучшение — сортировка с гарантией O(k log k) внутри бакета, тогда худший случай O(n log n).
- «Чем отличается от counting sort?» Counting sort — бакет на каждое значение, внутри сортировать не надо, но память O(k) на диапазон. Bucket sort — бакетов около n, зато нужна сортировка внутри и важна равномерность.
- «Можно ли быстрее O(n log n) в Top K Frequent?» Да, бакеты по частоте.
- «Решите Maximum Gap за O(n)». Принцип Дирихле: ответ не меньше
(max − min) / (n − 1), значит, он лежит между бакетами.
Если хочется систематизировать все сортировки разом, загляните в сравнение алгоритмов сортировки.
Что запомнить
- Bucket sort = раскладка по диапазонам без сравнений + сортировка маленьких бакетов + склейка.
- O(n) — ожидаемое время при равномерных данных и m ≈ n; при перекосе деградирует до сложности внутренней сортировки.
- Counting sort — частный случай с бакетом шириной в одно значение, radix sort — серия раскладок по цифрам.
- На собеседованиях бакеты — это прежде всего приём: Maximum Gap (min/max в бакете), Top K Frequent (бакет на частоту), почти-дубликаты в окне (бакеты шириной t + 1).
- Всегда проверяйте граничные случаи: пустой массив, все элементы равны, максимум на правой границе, отрицательные числа.