Устойчивость и сортировка по ключу

Если ты знаешь, что такое ключ и устойчивость, умеешь сортировать по нескольким полям через устойчивость (от менее важного ключа к более важному) и помнишь, какие сортировки устойчивы, листай до «Теперь сам».

Как думаешь, что именно сравнивают, когда сортируют реальные данные

В жизни сортируют не числа сами по себе, а ЗАПИСИ: список сотрудников, заказов, файлов. И упорядочивают их по какому-то одному полю - по возрасту, по дате, по имени. Это поле и называют ключом. Сортировка сравнивает записи ТОЛЬКО по ключу, а всё остальное поле несёт с собой как «груз». И тут возникает вопрос, которого нет у голых чисел: а что делать с записями, у которых ключ ОДИНАКОВЫЙ? Их можно оставить как были, а можно переставить - и от этого выбора зависит очень многое.

На что это похоже

Стопка личных дел, которую надо разложить по годам рождения. Два человека родились в один год - в каком порядке класть их дела? «Устойчивый» архивариус оставит их в том порядке, в каком они лежали (скажем, по алфавиту, как было раньше). «Неустойчивый» - бросит как попало. Пока тебе нужен только год - разницы нет. Но если дела УЖЕ были разложены по алфавиту, а ты сверху раскладываешь по годам, то устойчивость сохранит алфавит внутри каждого года - и ты получишь порядок «по году, а внутри года по алфавиту» БЕСПЛАТНО.

Механизм: ключ, устойчивость и композиция

Ключ. Сортировка сравнивает записи по значению ключа (запись.возраст, запись[0]), а перемещает запись целиком. Одну и ту же структуру можно сортировать по разным ключам.

Устойчивость. Сортировка УСТОЙЧИВА, если записи с равным ключом сохраняют свой исходный взаимный порядок. Формально: если во входе запись A стояла раньше B и их ключи равны, то и в выходе A раньше B.

Композиция по нескольким ключам. Чтобы отсортировать по «первичному ключу, а внутри равных - по вторичному», делают два прохода УСТОЙЧИВОЙ сортировкой: сначала по ВТОРИЧНОМУ ключу, потом по ПЕРВИЧНОМУ. Второй проход расставляет первичный ключ, а устойчивость сохраняет уже наведённый порядок по вторичному внутри равных первичных.

Правило

Ключ - поле, по которому сравнивают записи (перемещая их целиком). Сортировка УСТОЙЧИВА, если записи с равным ключом сохраняют исходный взаимный порядок. Устойчивость позволяет собирать многоключевую сортировку: сортируй по ключам от МЕНЕЕ важного к БОЛЕЕ важному устойчивой сортировкой. Устойчивы вставками, слияние и подсчётом; неустойчивы выбором, быстрая, пирамидальная и Шелла.

Разбор: почему для многоключевой сортировки идут от менее важного ключа

Порядок проходов - от ВТОРИЧНОГО (менее важного) к ПЕРВИЧНОМУ (более важному) - и он не случаен. Более важный ключ должен сортироваться ПОСЛЕДНИМ, чтобы задать главный порядок. А внутри записей с равным первичным ключом порядок берётся из ПРЕДЫДУЩЕГО прохода - по вторичному ключу, - и держится он только потому, что последний проход УСТОЙЧИВ. Проверь на записях [класс, балл]: сначала сортируем по баллу (вторичный) - получаем записи по возрастанию балла; потом устойчиво по классу (первичный) - классы встают по порядку, а внутри каждого класса баллы остаются возрастающими (устойчивость не тронула их взаимный порядок). Пойди мы в обратном порядке (сначала по классу, потом по баллу) - второй проход по баллу перемешал бы классы, и всё сломалось бы. Менее важный - раньше, более важный - последним и устойчиво: вот рецепт.

Разбор: какие сортировки устойчивы и почему

Устойчивость - свойство конкретного алгоритма, и зависит она от того, переставляет ли он ДАЛЁКИЕ элементы. Вставками устойчива: она сдвигает только элементы строго больше ключа (>), поэтому равные не перепрыгивают друг друга. Слияние устойчиво: при слиянии равных берут элемент из ЛЕВОЙ (более ранней) части. Подсчётом устойчива (в варианте с префиксными суммами). А вот быстрая, пирамидальная, выбором и Шелла - НЕустойчивы: все они меняют местами далёкие элементы (разбиение вокруг опорного, просеивание кучи, выбор минимума, прыжки Шелла), и равные при этом легко меняются местами. Практический вывод: нужна устойчивость - бери слияние (или встроенную сортировку объектов, она обычно устойчива); можно без неё - подойдёт и быстрая.

Что ломается без этого

Первая ошибка - взять НЕустойчивую сортировку для второго прохода многоключевой сортировки: порядок по предыдущему ключу разрушится, и внутри равных первичных ключей вторичный окажется перемешан. Именно эту ошибку допускает наивная попытка «отсортирую по классу» - она не сохраняет порядок по баллу. Вторая ошибка - думать, что устойчивость «всегда нужна» или «всегда бесплатна»: если ключ уникален (равных нет вовсе) или порядок равных не важен, устойчивость не нужна, и можно взять более быструю неустойчивую сортировку. Устойчивость - инструмент под задачу, а не всегдашнее требование.

Зачем это в работе

Многоключевая сортировка - повседневность: таблица, которую пользователь сортирует по одному столбцу, потом по другому, ожидая, что прошлый порядок сохранится (кликнул «по дате», потом «по имени» - записи с одинаковым именем остались по дате). Это работает ровно потому, что стандартная сортировка объектов УСТОЙЧИВА. В Python list.sort и sorted устойчивы и принимают key=: records.sort(key=...). Чтобы отсортировать по двум полям, можно либо передать ключом кортеж (первичный, вторичный), либо (когда так нельзя) сделать два устойчивых прохода от менее важного ключа к более важному. Понимать устойчивость - значит уметь получать сложные порядки, не написав ни одной сложной сортировки.

Теперь сам

Записи [город, имя] надо упорядочить по городу, а внутри города - по имени. В каком порядке делать проходы устойчивой сортировкой и почему именно так, а не наоборот?