Сортировка, поиск и обход

Что это такое

Три семейства процедур решают почти всю алгоритмическую работу в обычном программном обеспечении. Поиск находит значение в коллекции, сортировка приводит коллекцию в порядок, чтобы дальнейшие вопросы стали дешёвыми, а обход посещает всё, что достижимо по набору связей. В каждом семействе есть небольшой набор стандартных участников, и каждый несёт известную стоимость, которая говорит, где ему место.

Почему это важно

Узнавание этих процедур избавляет вас от написания более медленной версии того, что уже существует. Сортировка — не служебный вызов, а решение: устойчивость, расход памяти и форма входа меняют то, какая сортировка верна, а неверный выбор невидим, пока данные не вырастут. А обход подводит молча: если проверки посещённого нет, обход небольшого графа превращается в бесконечный цикл в продакшене.

Ключевые идеи

Линейный поиск против двоичного

Сканирование списка проверяет элементы, пока не найдёт совпадение, поэтому стоимость растёт с числом элементов. Если список отсортирован, двоичный поиск на каждом шаге вдвое сокращает оставшийся диапазон и находит значение среди миллиона за двадцать сравнений. Компромисс явный: сортировка сначала стоит один линейно-логарифмический проход, зато каждый дальнейший поиск логарифмичен — это оправдано начиная с нескольких поисков, но не для одного.

отсортировано: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
искомое 23
low 0, high 9 -> mid 4 (16) -> 23 > 16 -> low 5
low 5, high 9 -> mid 7 (56) -> 23 < 56 -> high 6
low 5, high 6 -> mid 5 (23) -> найдено за 3 шага

Сортировки сравнениями и их стоимость

Сортировка сравнениями определяет порядок, спрашивая «идёт ли a перед b». Лучшей возможной такой сортировке нужно около n log n сравнений. Известные сортировки — слиянием, быстрая, пирамидальная — все лежат в этом классе с разными постоянными множителями и режимами отказа. Сортировка слиянием устойчива, но требует дополнительной памяти. Быстрая сортировка работает на месте и обычно самая быстрая, но вырождается в квадратичную на враждебном входе, если опорный элемент выбран небрежно. Пирамидальная гарантирует границу независимо от порядка входа.

вход: [5, 2, 9, 1]
сортировка слиянием: разбить, отсортировать половины, слить
  [5, 2] -> [2, 5]      [9, 1] -> [1, 9]
  слияние -> [1, 2, 5, 9]

Подходы на хешах и подсчётом

Когда сортировка сравнениями не обязательна, стоимость может опуститься ниже n log n. Если нужны только различные значения, хеш-множество делает один линейный проход. Если значения — небольшие целые в известном диапазоне, их подсчёт сортирует за линейное время. Условие каждый раз одно: алгоритм использует в данных то, чего сортировка сравнениями предполагать не может.

значения в диапазоне 0..9: подсчитать каждое в таблицу из десяти ячеек,
затем вывести каждое значение столько раз, сколько насчитано.

Стоимость обхода деревьев и графов

На каждый узел дерева при посещении приходится один шаг, ведь к каждому ведёт ровно один путь. Граф устроен иначе: в нём бывают циклы и несколько путей к одному и тому же узлу, поэтому обход обязан помнить, где он уже побывал. Пока такая запись ведётся, поиск в ширину и в глубину идёт за время, пропорциональное числу узлов плюс рёбер; без неё работа никогда не заканчивается. Кратчайшие пути в невзвешенных графах находит поиск в ширину, а циклы распознаёт и топологический порядок выдаёт поиск в глубину.

visited = set()
stack = [start]
while stack not empty:
  node = stack.pop()
  if node in visited: continue
  visited.add(node)
  stack.extend(node.neighbours)

Практика

Сделайте поиск логарифмическим

Возьмите неотсортированный список, который вы ищете снова и снова. Отсортируйте его один раз, а сканирование замените двоичным поиском, написанным своими руками, — вместе со случаями пустого списка и ненайденного значения.

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

Докажите себе цикл

Постройте ориентированный граф с петлёй и запустите поиск в глубину, который запоминает узлы, находящиеся сейчас на пути. Напечатайте цикл, а затем запустите тот же код на ациклическом графе.

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

Частые ошибки

Двоичный поиск по неотсортированной коллекции — поиск молча возвращает неверный ответ на части входов вместо отказа; исправить: сначала отсортируйте коллекцию или применяйте линейное сканирование, пока данные неупорядочены.
Забыть множество посещённых при обходе графа — цикл превращает обход в бесконечный; исправить: записывайте узел в тот самый момент, когда он попадает в очередь.
Выбор сортировки без проверки устойчивости — записи с равными ключами возвращаются в разном порядке при каждом запуске; исправить: решите, нужна ли устойчивость, и выбирайте устойчивую сортировку, когда нужна.
Сортировка внутри цикла — переупорядочивание одних и тех же данных на каждой итерации множит стоимость впустую; исправить: сортируйте один раз вне цикла или поддерживайте порядок прямо по мере построения.
Доверие к среднему случаю на пути, чувствительном к задержке — редкий квадратичный вход приходит, когда трафик самый высокий; исправить: там, где важен дедлайн, предпочитайте гарантированную границу.

Что читать дальше

Как растёт стоимость (Big-O) (01-cs-fundamentals/14-algorithms-big-o/01-how-cost-grows-big-o) — запись, которой эта статья пользуется повсюду, поэтому прочитайте её первой.
Структуры данных (01-cs-fundamentals/02-data-structures) — структуры, по которым работают эти процедуры, и почему каждой из них подходит свой алгоритм.
Внутреннее устройство баз данных (01-cs-fundamentals/04-database-internals) — сортировка и поиск в масштабе диска, где константы перестают быть пренебрежимо малыми.