Сортировка с пользовательским компаратором

Сортировка с пользовательским компаратором: как это работает?

Компаратор берёт два элемента и возвращает число. Отрицательное значит, что первый идёт раньше.

Ноль значит, что элементы равны. Устойчивая сортировка оставит их в исходном порядке.

Для обычных чисел возвращайте a минус b по возрастанию. Избегайте вычитания, если значения могут переполниться.

При нескольких ключах сравните первый. К следующему переходите только при равенстве.

Правило обязано быть согласованным. Если a раньше b, а b раньше c, то a раньше c.

Компаратор вызывается n log n раз. Всё дорогое внутри него посчитайте один раз заранее.

1. [Аня 30, Боря 25, Слава 30]Сортируем сначала по возрасту, потом по имени.
2. сравнение(Аня, Боря)30 против 25 даёт положительное число. Боря идёт раньше.
3. сравнение(Аня, Слава)Возраст совпал на 30. Правило переходит к имени.
4. Аня раньше СлавыРешает второй ключ. Аня выигрывает по имени.
5. [Боря 25, Аня 30, Слава 30]Два ключа, один проход. Порядок теперь полный.

// sort by a custom / multi-key order
items.sort((a, b) => {
    if (a.priority !== b.priority) return a.priority - b.priority;
    return a.name.localeCompare(b.name);
});

Сортировка с пользовательским компаратором: разбор примера

Собрать из чисел наибольшее

Дан список неотрицательных целых. Расставьте их так, чтобы склеенные цифры читались как наибольшее число.

Верните строку, потому что результат бывает огромным.

Сортировка по значению здесь неверна: 9 обязана идти раньше 30.

Сравнивайте два числа по двум склейкам, которые из них получаются. Ставьте a первым, если a плюс b больше.

function largestNumber(nums) {
    const parts = nums.map(String);

    // whichever joined order reads larger wins the comparison
    parts.sort((a, b) => (b + a).localeCompare(a + b));

    if (parts[0] === "0") return "0"; // every value was zero
    return parts.join("");
}

Сортировка с пользовательским компаратором: когда применять?

Эти формулировки в условии ведут сюда:

• •сортировка по нескольким полям / разрешение ничьей по второму ключу
• •произвольный порядок (не простое возрастание)
• •сортировка по убыванию или по вычисляемому ключу
• •«отсортируй так, чтобы X шло перед Y, если...»
• •переупорядочивание объектов/записей, а не чисел

Сортировка с пользовательским компаратором: с чем путают?

• Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Та страница про то, как происходит сортировка. Эта про порядок, который вы заказываете.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Жадное рассуждение обычно и выбирает верный порядок. Компаратор это способ его записать.
• Интервалы: слияние и вставка (Intervals: merge & insert): Работа с интервалами начинается с сортировки по началу. Слияние это отдельный шаг после неё.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Куча берёт тот же компаратор, но держит только начало. Она нужна, когда данные ещё поступают.

Сортировка с пользовательским компаратором: частые ошибки

• Сортируют числа без компаратора

  JavaScript по умолчанию сравнивает как строки, поэтому 10 встаёт перед 9. Всегда передавайте компаратор.

• Вычитают очень большие значения

  Разность может переполниться или потерять точность. Возвращайте минус один, ноль или один.

• Пишут правило, противоречащее себе

  Несогласованный компаратор даёт неопределённый результат. Некоторые движки просто бросают ошибку.

• Считают дорогой ключ внутри него

  Компаратор вызывается на каждое сравнение, а не раз на элемент. Посчитайте ключ заранее.

Сортировка с пользовательским компаратором: задачи с собеседований

• Наибольшее число: Порядок по тому, какая из двух склеек больше.
• Слияние интервалов: Сортировка по началу идёт до всего остального.
• Переговорные комнаты: Та же сортировка, потом проверка каждой соседней пары.
• Сортировка по возрастанию частоты: Первый ключ это частота, второй само значение.
• Сортировка по заданному алфавиту: Порядок задан совсем другой строкой.
• Относительная сортировка массива: Сначала перечисленные значения, остальные по возрастанию.
• K ближайших точек к началу: Сортируйте по квадрату расстояния, а не по корню.

Сортировка с пользовательским компаратором: сложность по времени и памяти

O(n log n)

n до 1e6 даёт O(n log n) сравнений. Медленный компаратор умножает это, поэтому ключ считайте заранее.