Почему база данных всё время сортирует, отчего Python сортирует почти упорядоченный список за линейное время, откуда берётся n log n и как написать бинарный поиск без ошибки на единицу.
Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки и двигайте ползунки. Примеры кода — на Python.
sort | uniq -c и GroupAggregate в Postgres.ORDER BY, оконные функции, CREATE INDEX — тоже сортировка. Её цена видна в EXPLAIN.Типичный приём: заплатить O(n log n) один раз, а дальше всё делать линейными проходами.
from itertools import groupby
by_user = lambda r: r.user_id
logs.sort(key=by_user) # O(n log n) один раз
for user, rows in groupby(logs, by_user):
print(user, len(list(rows))) # группы идут подряд
# без sort groupby склеит только соседние — частый баг
def intersect(a, b): # оба отсортированы
i = j = 0 # O(n + m)
while i < len(a) and j < len(b):
if a[i] < b[j]: i += 1
elif a[i] > b[j]: j += 1
else: # совпало — как в merge join
yield a[i]; i += 1; j += 1
Выберите массив и нажмите «Пуск». Здесь быстрая сортировка наивная: опорный элемент — последний. Посмотрите, что с ней будет на отсортированном и обратном массиве.
std::sort, .NET): если рекурсия глубже 2·log₂n — переключаемся на heapsort. Гарантия O(n log n).slices.Sort, sort.Sort; Rust sort_unstable до ipnsort в 1.81): introsort + отдельная обработка повторов + распознавание уже упорядоченных кусков.Выберите данные и стратегию. Здесь n = 2000 и считаются настоящие сравнения.
Стабильная сортировка сохраняет исходный порядок элементов с равными ключами. Поэтому сортировку по нескольким ключам можно делать проходами: сначала по второстепенному, потом по главному.
staff.sort(key=lambda e: e.salary, reverse=True)
# внутри отдела останется порядок по зарплате:
staff.sort(key=lambda e: e.dept)
# то же за один проход:
staff.sort(key=lambda e: (e.dept, -e.salary))
Стабильны: Python sort, Java для объектов, JS Array.prototype.sort (по стандарту с ES2019), Go slices.SortStableFunc. Нестабильны: Go slices.Sort, C++ std::sort, Java Arrays.sort(int[]) — для чисел это и не важно.
minrun (32–64 элемента).Python list.sort (с 3.11 — стратегия слияний powersort), Java для объектов, V8, Android. Отсортированный список — n−1 сравнение. Выберите данные и нажимайте «Шаг».
Сортировка сравнениями — это дерево решений: в узле сравнение, в листе готовая перестановка. Листьев не меньше n!, значит, высота дерева — худшее число сравнений — не меньше log₂(n!) ≈ n log₂n − 1,44n.
Граница — для алгоритмов, которые только сравнивают. Counting и radix sort смотрят на сами ключи и её обходят. Нажмите на перестановку — подсветится путь по дереву для трёх элементов.
numpy.sort(kind='stable') для целых до 16 бит.Нажимайте «Шаг»: раскладка по текущему разряду, затем сбор корзин по порядку. Стабильность раскладки — ключ к тому, что следующий проход не портит предыдущий.
heapq.nlargest(10, items). Postgres для ORDER BY … LIMIT 10 пишет Sort Method: top-N heapsort.numpy.partition, C++ nth_element — introselect.Ищем медиану. Нажимайте «Шаг»: после разбиения опорный элемент стоит на своём окончательном месте, и половину массива можно больше не смотреть.
work_mem: в плане Sort Method: external merge Disk: …. Подробнее о памяти — в «PostgreSQL изнутри».sort (-S задаёт буфер) и слияние сегментов в LSM-деревьях.Здесь «память» вмещает 6 записей. Нажимайте «Шаг».
Заказы уже отсортированы по дате. Делаем orders.sort(key=lambda o: o.status). В каком порядке окажутся заказы внутри одного статуса?
slices.SortStableFunc; обычный slices.SortFunc (pdqsort) порядок равных не сохраняет.
def lower_bound(a, x):
lo, hi = 0, len(a) # ответ в [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # a[..mid] < x
else:
hi = mid # a[mid..] >= x
return lo # первый a[i] >= x
Пишите от инварианта: «слева от lo всё < x, начиная с hi — всё ≥ x». Отрезок каждый раз строго сужается, а ответ из него не выпадает. upper_bound отличается одним знаком: a[mid] <= x.
bisect (с 3.10 — параметр key), Go sort.Search и slices.BinarySearch, C++ lower_bound. Java Collections.binarySearch при промахе возвращает -(точка вставки) - 1.(lo + hi) / 2 переполняет int в Java и C — этот баг 9 лет жил в JDK. Пишут lo + (hi - lo) / 2 или (lo + hi) >>> 1..index-файлах Kafka, блоки SSTable, git bisect — бинарный поиск по истории коммитов.
import bisect
a = [10, 20, 20, 20, 30]
bisect.bisect_left(a, 20) # 1 — первый >= 20
bisect.bisect_right(a, 20) # 4 — первый > 20
# сколько двадцаток: 4 - 1 = 3, за O(log n)
def grade(score, bounds=(60, 70, 80, 90)):
return 'FDCBA'[bisect.bisect_right(bounds, score)]
grade(85) # 'B'
bisect.insort(events, e) # O(log n) на поиск,
# но O(n) на сдвиг списка!
# много вставок — sortedcontainers.SortedList
Ищем не элемент, а минимальное значение, при котором проверка проходит. Условие одно: проверка монотонна — если вместимости c хватает, хватит и c + 1.
def ship_within_days(w, days):
def fits(cap): # жадно грузим по порядку
need, load = 1, 0
for x in w:
if load + x > cap:
need, load = need + 1, 0
load += x
return need <= days
lo, hi = max(w), sum(w) # ответ в [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
if fits(mid): hi = mid
else: lo = mid + 1
return lo # O(n · log(sum))
Признаки в условии: «минимально возможное максимальное», «наименьшая скорость, чтобы успеть», «за D дней».
Отсортированный массив сдвинули по кругу: [15, 18, … 31, 2, 5, … 13]. Целиком он не упорядочен, но в каждом отрезке [lo, hi] хотя бы одна половина от mid отсортирована. Проверяем, лежит ли цель в ней, — и отбрасываем другую.
if a[lo] <= a[mid]: # левая половина ровная
if a[lo] <= x < a[mid]: hi = mid - 1
else: lo = mid + 1
else: # ровная — правая
if a[mid] < x <= a[hi]: lo = mid + 1
else: hi = mid - 1
Выберите, что искать, и нажимайте «Шаг». Цветом выделена отсортированная половина.
range_agg в Postgres, поиск пересечений в геометрии.Обе задачи — O(n log n) из-за сортировки, сам проход линейный. Выберите режим и нажимайте «Шаг».
Перед решением уточните: нужна ли стабильность, можно ли менять входной массив, какой диапазон значений и есть ли повторы. Каждый ответ меняет выбор алгоритма.
Сортируем миллион строк: sorted(words, key=str.lower). Сколько раз вызовется str.lower?
cmp: функция сравнения вызывалась бы на каждом сравнении. Если без неё никак — functools.cmp_to_key, и это в разы медленнее. В JS компаратор вызывается на каждое сравнение, а без него [10, 9, 1].sort() сравнивает строки и даёт [1, 10, 9].Что вернёт sorted(['яблоко', 'Ёлка', 'арбуз', 'ёж', 'Банан'])?
Ё = U+0401 стоит перед всеми заглавными, ё = U+0451 — после я, а все заглавные — перед строчными. Для человеческого порядка нужна collation: key=locale.strxfrm с ru_RU.UTF-8 или ICU (PyICU). В Postgres порядок ORDER BY и индексов задаёт collation колонки, и обновление glibc 2.28 однажды поменяло его так, что индексы пришлось перестраивать.
EXPLAIN (ANALYZE) SELECT * FROM orders
ORDER BY created_at LIMIT 10;
-- Sort Method: top-N heapsort Memory: 27kB
EXPLAIN (ANALYZE) SELECT * FROM orders ORDER BY total;
-- Sort Method: external merge Disk: 181240kB
-- не влезло в work_mem: поднять для сессии или
-- дать индекс, который отдаёт строки уже по порядку
from timeit import timeit
import random
a = list(range(10**6))
b = random.sample(a, len(a))
timeit(lambda: sorted(a), number=10) # ~0,2 с
timeit(lambda: sorted(b), number=10) # ~11 с
# отсортированный вход — одна серия, n − 1 сравнение
$ sort -S 2G --parallel=8 big.csv > out.csv
heapq.nsmallest, LIMIT с индексом.SortedList, B-дерево или куча, а не insort в список.key, а не через компаратор. Для массивов чисел — numpy.sort: тот же алгоритм, но без объектов Python.slices.Sort и C++ std::sort — нет.Отсортируй — и задача станет проходом.