Как отсортировать миллион чисел и не сойти с ума
Разложить колоду из 52 карт по порядку легко. А миллион чисел? Если действовать в лоб, компьютер будет молотить часами. Разбираемся, как пара хитрых идей превращает вечность в доли секунды.
Представь стопку из миллиона карточек с числами, которые нужно разложить по возрастанию. Кажется, тут одна задача. На самом деле — десятки способов её решить, и разница между ними не «чуть медленнее», а «секунда против целого дня». Давай разберёмся, почему так и какой фокус прячут за словами «быстрая сортировка».
Самый честный способ — и почему он бесит
Начнём с того, как сортируют люди, когда никто не учил их умному. Берёшь два соседних числа, сравниваешь. Если левое больше правого — меняешь их местами. Идёшь дальше, до конца ряда. Потом возвращаешься в начало и повторяешь всё заново. И снова. Пока за целый проход не окажется ни одной перестановки — значит, всё уже по порядку.
Этот способ называется пузырьковой сортировкой: большие числа медленно «всплывают» к концу, как пузырьки воздуха в стакане газировки. Он честный, понятный и его легко написать в десять строк. Проблема в другом — он чудовищно медленный.
Прикинем. Чтобы навести порядок среди n чисел, пузырьку в худшем случае нужно примерно n раз пройтись по всему ряду, а каждый проход — это около n сравнений. Перемножаем: получается порядка n × n операций. Для миллиона чисел это миллион, умноженный на миллион — триллион действий. Даже шустрый компьютер, делающий сотни миллионов операций в секунду, провозится с этим часами. Вот тут обычно и хочется сойти с ума.
Фокус в том, чтобы делить
Умные алгоритмы не пыхтят над всем массивом сразу. Они пользуются хитростью, которую называют «разделяй и властвуй». Идея до смешного простая: большую задачу режут на половинки, половинки — ещё на половинки, и так до тех пор, пока не останутся кусочки, с которыми справится и младенец.
Вот тебе аналогия. Представь, что вам с классом из тридцати человек надо разложить по порядку огромную колоду карт. Глупо отдавать всю колоду одному — он будет копаться вечность. Умнее раздать каждому по маленькой пачке. Каждый быстро раскладывает свою — это просто, карт-то мало. А дальше вы попарно сливаете отсортированные пачки в одну, потом сливаете слитое, и за несколько шагов вся колода оказывается в идеальном порядке.
Именно так работает сортировка слиянием (merge sort). Она дробит массив пополам, пока не останутся кусочки по одному числу (а одно число уже «отсортировано» само по себе), а затем аккуратно соединяет соседей обратно, на каждом шаге сравнивая их «головы» и выбирая меньшую.
Гениальные алгоритмы редко придумывают новый супер-приём. Чаще они просто перестают делать лишнюю работу.
Магические буквы n log n
Теперь — почему это не просто «чуть быстрее», а быстрее в тысячи раз. Когда ты делишь миллион пополам, потом ещё пополам и так далее, до единицы ты доберёшься всего за двадцать с небольшим шагов. Не верится? Проверь: 2 в двадцатой степени — это уже больше миллиона. Удвоение растёт неприлично быстро, а значит, деление пополам неприлично быстро уменьшает.
Этих «уровней деления» получается примерно log n штук. На каждом уровне мы один раз проходим по всем n числам, когда сливаем кусочки. Итог — около n × log n операций. Информатики записывают это как O(n log n) и произносят «о большое от эн лог эн». Сравни сам, что это значит для миллиона чисел:
- Пузырьковая, O(n²): около триллиона операций — это долгие часы работы.
- Слиянием, O(n log n): около двадцати миллионов операций — доли секунды.
Разница не в проценты. Это как сходить пешком в соседний город против перелёта на самолёте: вроде та же цель, но порядок времени совсем другой.
Быстрая сортировка: ставка на удачу
Есть ещё одна звезда, которую так и зовут — быстрая сортировка (quicksort). Её придумал британец Тони Хоар ещё в конце 1950-х, и до сих пор именно она крутится внутри множества программ по всему миру.
Работает она так. Из массива выбирают одно число — его называют опорным. Дальше все числа меньше опорного отправляют налево, все большие — направо. Теперь опорное стоит ровно на своём месте, а задача распалась на две поменьше — левую кучку и правую. К каждой применяют тот же приём, и так рекурсивно, пока кучки не схлопнутся в одиночные числа.
В среднем quicksort тоже выдаёт честные O(n log n) и на практике частенько обгоняет сортировку слиянием, потому что почти не требует дополнительной памяти. Но у неё есть капризный характер: если опорное число всё время выбирать неудачно — например, всегда самое маленькое, — она выродится в ту же тоскливую O(n²). Поэтому опорное часто берут случайным: немного удачи защищает от худшего случая.
Так что выбрать, чтобы не сойти с ума
Хорошая новость: тебе почти никогда не придётся писать всё это руками. В Python есть sorted(), в JavaScript — .sort(), и внутри них уже зашиты выверенные годами алгоритмы (часто — умные гибриды слияния и других приёмов). Они отсортируют твой миллион чисел за мгновение, и ты даже не заметишь.
Но знать, что там внутри, всё равно полезно. Это и есть главный секрет: дело не в том, чтобы компьютер считал быстрее, а в том, чтобы он считал меньше. Один и тот же миллион чисел можно перебирать триллион раз, а можно — двадцать миллионов. Разница между «не сойти с ума» и «сойти» — это всего лишь правильно выбранный алгоритм. Загляни в любую сортировку чуть глубже, чем sorted(), — и ты начнёшь видеть эту магию повсюду.