Где применяется
1. Задача
Бинарный поиск работает только на отсортированных данных. Сортировка их такими и делает. А на упорядоченных данных решается целый ряд новых задач: слить пересекающиеся диапазоны, составить расписание, найти самый загруженный момент.
У тебя таблица лидеров в игре. Наверху должен стоять самый большой счёт. Если счёт у двоих одинаковый, выше тот, кто финишировал быстрее, то есть у кого меньше время. Если совпало и время, порядок решает имя, по алфавиту. Выходит, порядок зависит сразу от трёх вещей, и у каждой свой приоритет.
JavaScript умеет сортировать массив, но без подсказки знает только одно правило, и оно неожиданное. [2, 10, 1].sort() даёт [1, 10, 2]. Сортировка превратила числа в текст и сравнила текст. Символ "1" идёт раньше символа "2", поэтому "10" встало перед "2".
Любой порядок, кроме текстового, нужно задать самому. Правило записывают в виде маленькой функции. Её называют компаратором (от английского compare, сравнивать).
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входит[{ priority: 2, name: "cat" }, { priority: 1, name: "eve" }, { priority: 2, name: "ann" }, { priority: 3, name: "bob" }, { priority: 1, name: "dan" }].sort(cmp)| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| priority | 2 | 1 | 2 | 3 | 1 |
| name | cat | eve | ann | bob | dan |
Сортируем по priority, а по name только при равных priority. Компаратор вызывается из сортировки вставками, чтобы был виден каждый вызов.
Как узнать
Эти слова в условии значат этот паттерн
- сортировка по нескольким полям / разрешение ничьей по второму ключу
- произвольный порядок (не простое возрастание)
- сортировка по убыванию или по вычисляемому ключу
- «отсортируй так, чтобы X шло перед Y, если...»
- переупорядочивание объектов/записей, а не чисел
Похоже, но не то
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Та страница про то, как происходит сортировка. Эта про порядок, который вы заказываете.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадное рассуждение обычно и выбирает верный порядок. Компаратор это способ его записать.
- Интервалы: слияние и вставка (Intervals: merge & insert)
Работа с интервалами начинается с сортировки по началу. Слияние это отдельный шаг после неё.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Куча берёт тот же компаратор, но держит только начало. Она нужна, когда данные ещё поступают.
n до 1e6 даёт O(n log n) сравнений. Медленный компаратор умножает это, поэтому ключ считайте заранее.
На LeetCode
Задачи, где порядок задаёт правило, которое пишешь ты, например по частоте, а потом по значению, по порядку из другой строки, по расстоянию или по тому, какая склейка строк больше. Один компаратор возвращает отрицательное число, положительное или ноль.
Два ключа, которые проверяются по очереди, частота по возрастанию, затем значение по убыванию.
Компаратор вычитает позиции двух букв в строке order.
Сравнивай квадраты расстояний, x * x + y * y, и бери первые k.
Ставь a перед b, если строка a + b больше строки b + a.