Встроенная сортировка: sorted, sort и key

sorted(a) – функция: исходный список не трогает и возвращает новый. a.sort() – метод: переставляет элементы внутри самого списка и возвращает None.

temps = [5, -3, 7, 0, -8, 2, -1]

print(sorted(temps))   # [-8, -3, -1, 0, 2, 5, 7]
print(temps)           # [5, -3, 7, 0, -8, 2, -1]

temps.sort()
print(temps)           # [-8, -3, -1, 0, 2, 5, 7]

Главная ошибка – a = a.sort(). Метод честно сортирует список и возвращает None; это None и попадает в a, а упорядоченный список теряется. print(a) напечатает None.

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

Обе формы принимают reverse=True: sorted(temps, reverse=True) даёт [7, 5, 2, 0, -1, -3, -8]. Меняется направление самого сравнения, поэтому равные элементы сохраняют исходный порядок – после sort() и reverse() он был бы обратным.

Параметр key говорит сортировке, какую характеристику элемента сравнивать.

words = ['дом', 'информатика', 'кот', 'алгоритм']
print(sorted(words, key=len))
# ['дом', 'кот', 'алгоритм', 'информатика']

names = ['Пётр', 'анна', 'Борис', 'вера']
print(sorted(names))
# ['Борис', 'Пётр', 'анна', 'вера']
print(sorted(names, key=str.lower))
# ['анна', 'Борис', 'вера', 'Пётр']

temps = [5, -3, 7, 0, -8, 2, -1]
print(sorted(temps, key=abs))
# [0, -1, 2, -3, 5, 7, -8]

Имя функции пишется без скобок: key=len, а не key=len(). Ключ не меняет элементы: key=str.lower выстраивает слова так, будто все они строчные, но в результате буквы остаются как были.

Без key строки сравниваются по кодам символов. Поэтому '10' < '9' – первый символ 1 меньше 9, – а заглавные буквы идут раньше строчных. Лечится это key=str.lower или переводом строк в числа.

Кортежи и списки Python сравнивает поэлементно: сначала первые элементы, при равенстве – вторые. Поэтому sorted([(класс, фамилия), ...]) упорядочит пары по классу, а внутри класса – по фамилии.

Если нужен порядок по второму полю, поля в кортеже переставляют. Если нужно по убыванию числа, в кортеж кладут его с минусом: -x.

results = [(5, 'Быков'), (4, 'Орлов'), (5, 'Анохин'),
           (3, 'Ким'), (4, 'Волкова')]

prepared = []
for score, surname in results:
    prepared.append((-score, surname))
prepared.sort()

for score, surname in prepared:
    print(-score, surname)

Вывод: сначала пятёрки по алфавиту, потом четвёрки, потом тройка.

5 Анохин
5 Быков
4 Волкова
4 Орлов
3 Ким

reverse=True здесь не подходит: он переворачивает порядок по всем признакам сразу, и фамилии внутри равных баллов пойдут от конца алфавита.

Встроенная сортировка Python устойчива – это гарантировано документацией: элементы с одинаковым ключом остаются в прежнем взаимном порядке.

Отсюда приём: сортировать в два захода. Сначала по второстепенному признаку, потом по главному – и внутри одинаковых главных значений второстепенный порядок сохранится.

words = ['кот', 'дом', 'сон', 'море', 'ель', 'небо']

words.sort()
print(words)
# ['дом', 'ель', 'кот', 'море', 'небо', 'сон']

words.sort(key=len)
print(words)
# ['дом', 'ель', 'кот', 'сон', 'море', 'небо']

Второй вызов расставил слова по длине, а внутри одинаковой длины сохранил алфавитный порядок, хотя key=len про алфавит ничего не знает. Последний заход – главный: требование «по длине, при равенстве по алфавиту» выполняется двумя вызовами в обратном порядке.

Алгоритм называется Timsort: его написал Тим Петерс в 2002 году. Это гибрид сортировки вставками и слияния: сначала алгоритм ищет в данных готовые упорядоченные куски, а потом склеивает их между собой. На почти упорядоченных данных он заканчивает заметно раньше, чем предсказывает оценка.

Оценка – $O(N \log N)$ для любого входа.

Миллион чисел, поданный в разном порядке:

Для сравнения: самодельный пузырёк на 8 000 чисел тратит 3,9 с. Встроенная сортировка на 8 000 – 0,0006 с.

Почти никогда. Свою сортировку пишут ради понимания её цены и приёмов: разбиения, двух указателей, двоичного поиска. Эти приёмы понадобятся в задачах, где готовой функции нет.

Отдельная ловушка – сортировка внутри цикла. Каждый вызов sort() стоит $N \log N$, и цикл из N шагов превращает программу в $O(N^2 \log N)$, хотя выглядит как один проход. Если данные не меняются, сортируют один раз до цикла.