Сортировка и что она упрощает

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

a = [3, 8, 1, 9]

b = sorted(a)      # новый список [1, 3, 8, 9], a не тронут
a.sort()           # сам a стал [1, 3, 8, 9], ничего не возвращает

Разница ровно та же, что была у строк и списков раньше: одно средство создаёт новое, другое меняет на месте.

Последняя строка — ловушка из занятия про ссылку и копию, только в новом обличье. sort ничего не возвращает, поэтому присваивать его результат бессмысленно.

Обратный порядок задаётся аргументом:

print(sorted(a, reverse=True))    # [9, 8, 3, 1]

Как сортировка устроена внутри, мы разберём в шестом модуле. Пока достаточно знать, что она быстрая: сто тысяч чисел упорядочиваются мгновенно.

Иногда сравнивать нужно не сами значения, а что-то, посчитанное по ним: модуль числа, длину слова.

Для этого у сортировки есть аргумент key — функция, которая по элементу вычисляет признак:

print(sorted(a, key=abs))              # по модулю: [1, -3, 5, -8]
print(sorted(words, key=len))          # слова по длине
print(sorted(a, key=abs, reverse=True))  # по убыванию модуля

Сортируются при этом сами элементы — просто сравниваются они по признаку.

Сортировка устойчива. Это значит, что элементы с одинаковым признаком сохраняют свой прежний порядок. Если два слова одной длины, первым останется то, что раньше стояло в списке. Свойство не декоративное: на нём построены задачи, где просят «при равенстве — в исходном порядке».

Пока в качестве признака доступны готовые функции вроде abs и len. Свои собственные признаки — «по последней цифре», «по второму символу» — потребуют объявить функцию, а это тема пятого модуля.

a = [3, 1, 2]
b = a.sort()
print(b)

Что выведет программа?

Сортировка сама по себе ничего не решает. Ценна она тем, что после неё близкие по значению элементы оказываются рядом, а крайние — по краям.

Обратите внимание на две строки в середине. В прошлом занятии эти же задачи решались массивом счётчиков — но только когда значения невелики. Сортировка снимает это ограничение: ей всё равно, насколько большие числа.

Цена — время: сортировка не бесплатна, она делает порядка $n \log n$ действий. Для ста тысяч элементов это примерно в семнадцать раз больше, чем один проход, — то есть по-прежнему быстро.

Отсюда практическое правило: если задача про «какой по величине», «ближайшие», «одинаковые» — попробуйте мысленно отсортировать и посмотрите, что упростится.

Сортировка не универсальна, и есть два разных случая, когда её не надо.

Лишняя. Для суммы, среднего, количества подходящих элементов порядок не важен вовсе. sum(sorted(a)) — это sum(a), только медленнее. То же с максимумом: max(a) работает за один проход, а сортировка ради него — лишняя работа.

Вредна. Как только в вопросе есть слова «на каком месте», «первый по порядку», «сколько раз возросло» — сортировать нельзя: она уничтожает именно ту информацию, о которой спрашивают.

a.sort()
print(a.index(max(a)) + 1)     # номер максимума… но уже в новом порядке

Такая программа выдаёт осмысленное число, и потому ошибка не бросается в глаза. А число это — позиция в отсортированном списке, то есть почти всегда последняя.

Если нужны и порядок, и упорядоченность, делайте копию:

b = sorted(a)      # b упорядочен, a хранит исходный порядок

Это то же различие «на месте против копии», что и в занятии 18, и здесь оно стоит дороже: sort тихо портит данные, а заметить это можно только по ответу.

В списке 9 элементов. После упорядочивания по возрастанию медиана — это элемент с каким номером, если считать с единицы?

Введите целое число.

b = a.sort(). В b окажется None, а a окажется отсортирован. Признак: программа падает при попытке что-то сделать с b, или выводит None.

Порядок потерян. Отсортировали, а потом спросили про позицию. Признак: ответ похож на правдоподобный, но всегда один и тот же — вроде номера последнего элемента.

Сортировка вместо решения. Задачу «сколько инверсий» или «сколько раз элемент больше предыдущего» сортировка не решает, а делает бессмысленной: после неё ответ всегда одинаковый.

Как проверять себя

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

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

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

Задача: «дан список чисел; выведите номер позиции, на которой стоит наибольший элемент. Номера считаются с единицы, при нескольких наибольших — наименьший номер».

Ученик написал:

n = int(input())
a = list(map(int, input().split()))

a.sort()
print(a.index(a[-1]) + 1)

На входе 3 9 1 9 программа выводит 3, хотя верный ответ 2. Объясните, что она на самом деле посчитала, почему ошибка не бросается в глаза, и как её исправить.