Сортировка списка в Python

Сортировка означает расположение элементов коллекции в определённом порядке.

У некоторых типов есть естественный порядок. Числа упорядочены по значению: 1 идёт перед 2. Строки упорядочены по алфавиту: "four" идёт перед "one". Для всего остального или когда нужен другой порядок, вы задаёте пользовательский порядок с помощью функции-ключа: функции, которая превращает один элемент в значение, по которому его нужно сортировать.

Python сортирует списки двумя способами:

• sorted(s) возвращает новый отсортированный список и оставляет исходный без изменений. Она работает с любым итерируемым объектом.
• s.sort() сортирует список на месте: исходный порядок теряется.

Обе принимают одни и те же два именованных аргумента: key= (функция-ключ) и reverse=True для порядка по убыванию. Во многих языках сортировка выполняется с функцией сравнения, которая смотрит на два элемента; Python же просит ключ для одного элемента и сравнивает ключи. Почти любая функция сравнения, которую вы бы написали, превращается в более короткую функцию-ключ, например key=len для сортировки по длине.

В примерах ниже используются слова one, two, three, four.

Естественный порядок — это порядок, который есть у типа сам по себе: числа по значению, строки буква за буквой.

sorted(words) даёт новый список в естественном порядке. Для порядка по убыванию не нужно сортировать дважды: передайте reverse=True, и новый список получится перевёрнутым.

У кортежей тоже есть естественный порядок: Python сравнивает их позиция за позицией, и решает первое различие. Это бесплатно даёт порядок вашим собственным данным. Номер версии, хранящийся как кортеж (major, minor), сравнивается сначала по major, и только когда major равны, решает minor — это именно то многоразовое сравнение, которое иначе пришлось бы писать вручную.

sorted() создаёт новый список, отсортированный по алфавиту. Затем выводится исходный список words, чтобы показать, что он не изменился.

reverse=True заставляет sorted() вернуть новый список в порядке убывания, поэтому слова идут от "two" до "four".

Версия — это кортеж (major, minor). Сравнение кортежей сначала смотрит на major; только когда major равны, решает minor. (1, 2) > (1, 3) спрашивает «больше ли версия 1.2, чем 1.3?» и выводит False; (2, 0) > (1, 5) выводит True.

Пользовательский порядок — это любой порядок, который вы описываете функцией-ключом.

Передайте её как key=: Python вызывает функцию один раз для каждого элемента и сортирует элементы по тому, что она возвращает. Сортировка в Python устойчивая: элементы с равными ключами всегда сохраняют исходный порядок. Отдельная устойчивая сортировка вам никогда не нужна, например при сортировке слов по длине.

Сортировка по одному свойству каждого элемента — самый обычный случай: key=len сортирует по длине, а lambda позволяет выбрать что угодно другое, например последнюю букву слова.

Для порядка по убыванию добавьте reverse=True. Он переворачивает сравнение ключей, а равные элементы по-прежнему сохраняют исходный порядок.

Чтобы сортировать сначала по одному признаку, а затем по другому, возвращайте из функции-ключа кортеж. Кортежи сравниваются позиция за позицией, поэтому второй элемент разрешает ничью, когда первый говорит, что элементы равны.

key=len даёт каждому слову в качестве ключа его длину: 3 для "aaa", 2 для "bb", 1 для "c". Наименьший ключ идёт первым, поэтому слова располагаются от самого короткого к самому длинному. words.sort() делает это на месте.

Слова сортируются по key=len. "one" и "two" оба длиной 3 буквы; устойчивая сортировка оставляет "one" перед "two".

w[-1] — последняя буква слова. С reverse=True первым идёт слово с наибольшей последней буквой: "four" (r), затем "two" (o), затем два слова, оканчивающихся на «e», в их исходном порядке.

Ключ (len(w), w) — это кортеж: сначала длина. Когда два слова одинаковой длины, второй элемент — само слово — упорядочивает их по алфавиту.

Иногда нужно лишь узнать, отсортирован ли уже список, не сортируя его.

В Python нет функции is_sorted(), но проверка занимает одну строку: каждый элемент должен быть меньше или равен своему правому соседу. zip(s, s[1:]) объединяет в пару каждый элемент со следующим, а all() подтверждает, что каждая пара упорядочена. Для порядка по убыванию поменяйте сравнение: a >= b вместо a <= b.

Чтобы проверить порядок по одному свойству, например по возрасту пользователя, сравнивайте это свойство внутри проверки.

all(a <= b ...) подтверждает, что 1, 2, 3, 4 идут по возрастанию. Обратное сравнение a >= b подтверждает, что 4, 3, 2, 1 идут по убыванию.

Пользователи — Alice (24), Bob (31) и Charlie (29). Проверка смотрит только на возрасты. Bob старше, чем Charlie, поэтому список не отсортирован по возрасту, и программа выводит False.

Переворачивание ставит последний элемент первым, а первый — последним.

Срез words[::-1] создаёт перевёрнутую копию: исходный список сохраняет свой порядок. words.reverse(), напротив, переворачивает список на месте. Есть также встроенная функция reversed(words): она возвращает итератор, который проходит список в обратном направлении, не создавая новый, — оберните его в list(), когда нужен настоящий список.

Выводится копия, созданная с помощью words[::-1], затем выводится исходный список, чтобы показать, что он не изменился.

Перемешивание располагает элементы в случайном порядке.

В модуле random есть функция shuffle(). Как и words.reverse(), она работает на месте, поэтому перемешивайте копию, сделанную с помощью words[:], если исходный список ещё нужен.

Объект random.Random(seed) с фиксированным seed даёт один и тот же «случайный» порядок при каждом запуске программы с этим seed. Это полезно для тестов и для примеров вроде этого. У функции уровня модуля random.shuffle() нет фиксированного seed, поэтому порядок меняется при каждом запуске.

Объект random.Random с seed 25 перемешивает копию слов. С этим seed результат при каждом запуске — ['two', 'three', 'one', 'four'].