Информатика · объяснение и практика
Сравнение кортежей: решает первое различие, а не все координаты
Прослеживаем лексикографический порядок последовательностей, сравниваем общий префикс и связываем порядок полей составного ключа с главным критерием.

В теме Структуры данных · Учебная карта
Главная мысль
Кортежи одного вида сравниваются лексикографически: сначала первые элементы, затем при их равенстве вторые и далее. Первое различие решает весь порядок. Поэтому (2, 100) меньше (3, 0), хотя сто больше нуля. Это не требование, чтобы каждая координата первого кортежа была меньше соответствующей координаты второго. Если один кортеж является точным началом другого, короче означает меньше.
У первого поля есть приоритет
Представим пары целых чисел (день, номер). В паре (4, 90) первый элемент меньше, чем в (5, 1). На этом сравнение уже решено: девяносто и один не меняют результат. Если первые поля равны, например (4, 90) и (4, 12), приходится сравнить вторые. Тогда пара с двенадцатью идёт раньше.
Такой порядок напоминает словарный, но правило относится к последовательностям вообще. Он отличается от сравнения сумм: четыре плюс девяносто больше пяти плюс один, однако лексикографический результат противоположен. Сумма смешивает два поля в один показатель, а лексикографическое сравнение сохраняет приоритет первого. Для задачи нужно выбрать, какой именно смысл порядка требуется, а не считать оба варианта взаимозаменяемыми.
При равном начале важен факт окончания
Сравним (3, 7) и (3, 7, −100). Первые два элемента равны, затем первый кортеж заканчивается. Он меньше, хотя добавленное число во втором отрицательно. Правило не продолжает короткую последовательность воображаемыми нулями и не сравнивает отсутствующий элемент с минус ста. Общий префикс и длина являются отдельным граничным случаем.
Если все элементы и длина равны по сравнению, последовательности равны. Вложенные последовательности сравниваются по тому же правилу на своём уровне. При этом типы сравниваемых элементов должны поддерживать нужное сравнение. Например, целое и обычная строка не получают произвольного порядка по принципу «сначала все числа». Неожиданный TypeError в ключе может означать смешанные форматы данных, а не ошибку самого алгоритма сортировки.
Пример
Как упорядочатся по возрастанию пары (2, 50), (1, 90), (2, 7)?
Сначала идёт (1, 90), поскольку её первое поле меньше двух. Затем сравниваются две пары с первым полем два: семь меньше пятидесяти, поэтому идут (2, 7), затем (2, 50). Суммы полей здесь не вычислялись. При смене порядка полей результат мог бы стать другим, так как изменился бы главный критерий.
Перестановка полей меняет главный критерий
Если ключ записи равен (grade, name), сначала группирует оценка, затем имя среди одинаковых оценок. Если построить (name, grade), главным станет имя. Это изменение смысла, хотя набор двух полей остался тем же. Стабильность сортировки касается только случаев, когда весь выбранный ключ равен; она не отменяет явное сравнение второго элемента кортежа.
Для самопроверки возьмите две записи, у которых признаки спорят: первый критерий ставит одну раньше, второй другую. Такой пример обнаруживает перепутанный приоритет лучше пары, где оба поля одновременно возрастают. Затем отдельно проверьте одинаковое начало и разную длину. Нельзя выдавать лексикографическое сравнение за геометрическое расположение точки левее и ниже другой: это другой порядок и другая задача.
От чтения к действию
А теперь — вы
Частые вопросы
Все координаты должны быть меньше для меньшего кортежа?
Нет. Первое различающееся место определяет порядок, а последующие уже не участвуют.
Короткий равный префикс дополняют нулями?
Нет. Если одна последовательность является началом другой, меньшей считается короткая без вымышленных элементов.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Что сохраняет стабильная сортировка одинаковых ключей
Что означает стабильность сортировки, какой порядок сохраняется при равных ключах и как различаются sorted и изменение списка на месте в Python.
Открыть темуСортировка таблицы: почему переставлять нужно всю запись
Сохраняем связь между именем, номером и результатом при сортировке таблицы: рассматриваем перестановку целых записей и находим ошибку независимой сортировки одного столбца.
Открыть тему