Сортировка

Обзор

Сортировка - один из самых частых приемов на алгоритмическом интервью. Иногда задача прямо просит упорядочить данные, но чаще сортировка появляется как подготовительный шаг: после нее становится проще сравнивать соседние элементы, искать пары, объединять интервалы или убирать дубликаты.

Важно понимать, что сортировка не бесплатна. Обычно она добавляет O(n * log n) по времени, зато часто убирает вложенный цикл и превращает решение из O(n²) в O(n * log n). Если количество возможных элементов небольшое, то можно использовать сортировку подсчетом за O(n).

Сортировка подсчетом работает, когда диапазон значений небольшой. Мы один раз проходим по массиву и считаем, сколько раз встретилось каждое значение. Потом идем по диапазону от минимума до максимума и записываем элементы в нужном количестве.

Для массива длины n и диапазона значений k сложность равна O(n + k). Если k намного меньше n * log n, такой подход быстрее обычной сортировки. Когда k ограничен константой, например от 1 до 100, его можно не учитывать, и сложность можно считать O(n).

Это удобно в задачах, таких как Height Checker: рост учеников лежит в диапазоне от 1 до 100, поэтому можно обойтись без O(n * log n).

Идея паттерна

Когда массив отсортирован, порядок элементов сам по себе дает полезную информацию. Мы заранее знаем, что все меньшие элементы находятся слева, а большие - справа. Это позволяет делать выводы без полного перебора.

Например, если после сортировки два соседних элемента равны, значит в массиве есть дубликат. Если интервалы отсортированы по началу, то для проверки пересечения достаточно смотреть на текущий и предыдущий интервал. Если массив отсортирован по возрастанию, два указателя могут двигаться к нужной сумме без перебора всех пар.

Когда использовать

Сортировка часто помогает, когда в задаче есть такие признаки:

Нужно сравнивать элементы между собой, но порядок исходного массива не важен.
Нужно найти дубликаты, близкие значения или группы одинаковых элементов.
Нужно объединить или проверить интервалы.
Нужно найти пары или тройки с заданным свойством.
Можно пожертвовать исходным порядком ради более простого решения.

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

Что важно на интервью

На практике редко просят написать QuickSort или MergeSort с нуля. Чаще интервьюер проверяет, можете ли вы заметить, что сортировка меняет форму задачи.

Нужно уметь объяснить три вещи:

Почему после сортировки решение становится проще.
Не теряем ли мы важную информацию об исходном порядке.
Оправдана ли сложность O(n * log n).

Если сортировка используется только для удобства, интервьюер может спросить: "Можно ли решить за O(n)?" Часто ответом будет хеш-таблица, подсчет частот или специальный линейный алгоритм. Но сортировка все равно остается хорошей первой идеей, если она дает простое и корректное решение.

Пример

В задаче Height Checker нужно понять, сколько учеников стоят не на своих местах, если весь ряд должен быть отсортирован по росту.

Наивное решение - пытаться переставлять учеников вручную. Но проще сделать копию массива, отсортировать ее и сравнить с исходным массивом по индексам.

heights = [1, 1, 4, 2, 1, 3];
expected = [1, 1, 1, 2, 3, 4];

Индексы, где значения отличаются, показывают учеников, которые стоят не на своих местах.

Итоги

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