sorting.md
1> **Источник:** https://python-all.ru/3.16/howto/sorting.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# Методы сортировки89Встроенный метод [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort) изменяет список на месте. Также есть встроенная функция [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted), которая создаёт новый отсортированный список из итерируемого объекта.1011В этом документе рассматриваются различные методы сортировки данных с помощью Python.1213## Основы сортировки1415Простая сортировка по возрастанию выполняется очень легко: достаточно вызвать функцию [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted). Она возвращает новый отсортированный список:1617```pycon18>>> sorted([5, 2, 3, 1, 4])19[1, 2, 3, 4, 5]20```2122Также можно использовать метод [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort). Он изменяет список на месте (и возвращает `None`, чтобы избежать путаницы). Обычно он менее удобен, чем [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted), но если исходный список не нужен, он немного эффективнее.2324```pycon25>>> a = [5, 2, 3, 1, 4]26>>> a.sort()27>>> a28[1, 2, 3, 4, 5]29```3031Ещё одно различие: метод [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort) определён только для списков. В то время как функция [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted) принимает любой итерируемый объект.3233```pycon34>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})35[1, 2, 3, 4, 5]36```3738## Ключевые функции3940Метод [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort) и функции [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted), [`min()`](https://python-all.ru/3.16/library/functions.html#min), [`max()`](https://python-all.ru/3.16/library/functions.html#max), [`heapq.nsmallest()`](https://python-all.ru/3.16/library/heapq.html#heapq.nsmallest), [`heapq.nlargest()`](https://python-all.ru/3.16/library/heapq.html#heapq.nlargest) имеют параметр *key*, который задаёт функцию (или другой вызываемый объект), вызываемую для каждого элемента списка перед сравнением.4142Например, сравнение строк без учёта регистра с помощью [`str.casefold()`](https://python-all.ru/3.16/library/stdtypes.html#str.casefold):4344```pycon45>>> sorted("This is a test string from Andrew".split(), key=str.casefold)46['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']47```4849Значением параметра *key* должна быть функция (или другой вызываемый объект), принимающая один аргумент и возвращающая ключ для сортировки. Этот метод быстр, поскольку ключевая функция вызывается ровно один раз для каждой входной записи.5051Часто используется сортировка сложных объектов по некоторым их индексам. Например:5253```pycon54>>> student_tuples = [55... ('john', 'A', 15),56... ('jane', 'B', 12),57... ('dave', 'B', 10),58... ]59>>> sorted(student_tuples, key=lambda student: student[2]) # сортировка по возрасту60[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]61```6263Тот же подход работает для объектов с именованными атрибутами. Например:6465```pycon66>>> class Student:67... def __init__(self, name, grade, age):68... self.name = name69... self.grade = grade70... self.age = age71... def __repr__(self):72... return repr((self.name, self.grade, self.age))7374>>> student_objects = [75... Student('john', 'A', 15),76... Student('jane', 'B', 12),77... Student('dave', 'B', 10),78... ]79>>> sorted(student_objects, key=lambda student: student.age) # сортировка по возрасту80[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]81```8283Объекты с именованными атрибутами можно создать с помощью обычного класса, как показано выше, или они могут быть экземплярами [`dataclass`](https://python-all.ru/3.16/library/dataclasses.html#dataclasses.dataclass) или [именованного кортежа](https://python-all.ru/3.16/glossary.html#term-named-tuple).8485## Функции модуля operator и частичное вычисление функций8687Шаблоны [ключевых функций](https://python-all.ru/3.16/glossary.html#term-key-function), показанные выше, очень распространены, поэтому Python предоставляет удобные функции для упрощения и ускорения функций доступа. В модуле [`operator`](https://python-all.ru/3.16/library/operator.html#module-operator) есть [`itemgetter()`](https://python-all.ru/3.16/library/operator.html#operator.itemgetter), [`attrgetter()`](https://python-all.ru/3.16/library/operator.html#operator.attrgetter) и функция [`methodcaller()`](https://python-all.ru/3.16/library/operator.html#operator.methodcaller).8889Использование этих функций делает приведённые выше примеры проще и быстрее:9091```pycon92>>> from operator import itemgetter, attrgetter9394>>> sorted(student_tuples, key=itemgetter(2))95[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]9697>>> sorted(student_objects, key=attrgetter('age'))98[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]99```100101Функции модуля operator позволяют выполнять многоуровневую сортировку. Например, сортировка сначала по *оценке*, а затем по *возрасту*:102103```pycon104>>> sorted(student_tuples, key=itemgetter(1,2))105[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]106107>>> sorted(student_objects, key=attrgetter('grade', 'age'))108[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]109```110111Модуль [`functools`](https://python-all.ru/3.16/library/functools.html#module-functools) предоставляет ещё один полезный инструмент для создания ключевых функций. Функция [`partial()`](https://python-all.ru/3.16/library/functools.html#functools.partial) может уменьшить [арность](https://python-all.ru/3.16/howto/sorting.html) функции с несколькими аргументами, делая её пригодной для использования в качестве ключевой функции.112113```pycon114>>> from functools import partial115>>> from unicodedata import normalize116117>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()118119>>> sorted(names, key=partial(normalize, 'NFD'))120['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']121122>>> sorted(names, key=partial(normalize, 'NFC'))123['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']124```125126## По возрастанию и по убыванию127128Обе функции [`list.sort()`](https://python-all.ru/3.16/library/stdtypes.html#list.sort) и [`sorted()`](https://python-all.ru/3.16/library/functions.html#sorted) принимают параметр *reverse* с булевым значением. Он используется для указания сортировки по убыванию. Например, чтобы получить данные о студентах в обратном порядке по *возрасту*:129130```pycon131>>> sorted(student_tuples, key=itemgetter(2), reverse=True)132[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]133134>>> sorted(student_objects, key=attrgetter('age'), reverse=True)135[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]136```137138## Стабильность сортировки и сложные сортировки139140Сортировки гарантированно являются [стабильными](https://python-all.ru/3.16/howto/sorting.html). Это означает, что когда несколько записей имеют один и тот же ключ, их исходный порядок сохраняется.141142```pycon143>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]144>>> sorted(data, key=itemgetter(0))145[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]146```147148Обратите внимание, как две записи для *синего* сохраняют исходный порядок, так что `('blue', 1)` гарантированно предшествует `('blue', 2)`.149150Это замечательное свойство позволяет строить сложные сортировки в несколько этапов. Например, чтобы отсортировать данные о студентах сначала по убыванию *оценки*, а затем по возрастанию *возраста*, выполните сортировку по *возрасту* сначала, а затем снова отсортируйте по *оценке*:151152```pycon153>>> s = sorted(student_objects, key=attrgetter('age')) # сортировка по вторичному ключу154>>> sorted(s, key=attrgetter('grade'), reverse=True) # теперь сортировка по первичному ключу, по убыванию155[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]156```157158Это можно обобщить в функцию-обёртку, которая принимает список и кортежи из поля и порядка сортировки, чтобы выполнять сортировку в несколько проходов.159160```pycon161>>> def multisort(xs, specs):162... for key, reverse in reversed(specs):163... xs.sort(key=attrgetter(key), reverse=reverse)164... return xs165166>>> multisort(list(student_objects), (('grade', True), ('age', False)))167[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]168```169170Алгоритм [Timsort](https://python-all.ru/3.16/howto/sorting.html), используемый в Python, эффективно выполняет множественные сортировки, поскольку может использовать преимущества любого порядка, уже присутствующего в наборе данных.171172## Decorate-Sort-Undecorate173174Эта идиома называется Decorate-Sort-Undecorate по трём её шагам:175176- Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.177- Затем украшенный список сортируется.178- Наконец, украшения удаляются, создавая список, содержащий только исходные значения в новом порядке.179180Например, чтобы отсортировать данные о студентах по *оценке* с помощью подхода DSU:181182```pycon183>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]184>>> decorated.sort()185>>> [student for grade, i, student in decorated] # обратное преобразование186[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]187```188189Эта идиома работает, потому что кортежи сравниваются лексикографически: сравниваются первые элементы; если они одинаковы, то сравниваются вторые, и так далее.190191Не всегда строго необходимо включать индекс *i* в украшенный список, но его включение даёт два преимущества:192193- Сортировка стабильна – если два элемента имеют один и тот же ключ, их порядок сохранится в отсортированном списке.194- Исходные элементы не обязаны быть сравнимыми, поскольку порядок украшенных кортежей будет определяться максимум первыми двумя элементами. Так, например, исходный список может содержать комплексные числа, которые невозможно отсортировать напрямую.195196Другое название этой идиомы – [преобразование Шварца](https://python-all.ru/3.16/howto/sorting.html), по имени Рэндала Л. Шварца, который популяризировал её среди программистов на Perl.197198Теперь, когда сортировка в Python предоставляет ключевые функции, эта техника используется нечасто.199200## Функции сравнения201202В отличие от ключевых функций, которые возвращают абсолютное значение для сортировки, функция сравнения вычисляет относительный порядок для двух входных значений.203204Например, [чашечные весы](https://python-all.ru/3.16/howto/sorting.html) сравнивают два образца, давая относительное упорядочение: легче, равно или тяжелее. Аналогично, функция сравнения, такая как `cmp(a, b)`, вернёт отрицательное значение для «меньше», ноль, если входные значения равны, или положительное значение для «больше».205206Часто можно встретить функции сравнения при переводе алгоритмов с других языков. Кроме того, некоторые библиотеки предоставляют функции сравнения как часть своего API. Например, [`locale.strcoll()`](https://python-all.ru/3.16/library/locale.html#locale.strcoll) – это функция сравнения.207208Для таких случаев Python предоставляет [`functools.cmp_to_key`](https://python-all.ru/3.16/library/functools.html#functools.cmp_to_key) для обёртывания функции сравнения, чтобы сделать её пригодной для использования в качестве ключевой функции:209210```python211sorted(words, key=cmp_to_key(strcoll)) # порядок сортировки с учётом локали212```213214## Стратегии для неупорядочиваемых типов и значений215216При сортировке могут возникнуть различные проблемы с типами и значениями. Вот несколько стратегий, которые могут помочь:217218- Преобразуйте несравнимые входные типы в строки перед сортировкой:219220```pycon221>>> data = ['twelve', '11', 10]222>>> sorted(map(str, data))223['10', '11', 'twelve']224```225226Это необходимо, потому что большинство сравнений между разными типами вызывают [`TypeError`](https://python-all.ru/3.16/library/exceptions.html#TypeError).227228- Удалите специальные значения перед сортировкой:229230```pycon231>>> from math import isnan232>>> from itertools import filterfalse233>>> data = [3.3, float('nan'), 1.1, 2.2]234>>> sorted(filterfalse(isnan, data))235[1.1, 2.2, 3.3]236```237238Это необходимо, потому что [стандарт IEEE-754](https://python-all.ru/3.16/howto/sorting.html) предписывает: «Каждое NaN сравнивается неупорядоченно со всем, включая само себя».239240Аналогично, `None` можно удалить из наборов данных:241242```pycon243>>> data = [3.3, None, 1.1, 2.2]244>>> sorted(x for x in data if x is not None)245[1.1, 2.2, 3.3]246```247248Это необходимо, потому что `None` не сравнивается с другими типами.249250- Преобразуйте отображения в отсортированные списки элементов перед сортировкой:251252```pycon253>>> data = [{'a': 1}, {'b': 2}]254>>> sorted(data, key=lambda d: sorted(d.items()))255[{'a': 1}, {'b': 2}]256```257258Это необходимо, потому что сравнение словарей вызывает [`TypeError`](https://python-all.ru/3.16/library/exceptions.html#TypeError).259260- Преобразуйте множества в отсортированные списки перед сортировкой:261262```pycon263>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]264>>> sorted(map(sorted, data))265[['a', 'b', 'c'], ['b', 'c', 'd']]266```267268Это необходимо, потому что элементы множеств не имеют deterministic order – детерминированного порядка. Например, `list({'a', 'b'})` может дать либо `['a', 'b']`, либо `['b', 'a']`.269270## Разное271272- Для сортировки с учётом локали используйте [`locale.strxfrm()`](https://python-all.ru/3.16/library/locale.html#locale.strxfrm) в качестве ключевой функции или [`locale.strcoll()`](https://python-all.ru/3.16/library/locale.html#locale.strcoll) в качестве функции сравнения. Это необходимо, потому что «алфавитный» порядок сортировки может различаться в разных культурах, даже если базовый алфавит один и тот же.273- Параметр *reverse* сохраняет стабильность сортировки (так что записи с равными ключами сохраняют исходный порядок). Интересно, что этот эффект можно имитировать без параметра, дважды применив встроенную функцию [`reversed()`](https://python-all.ru/3.16/library/functions.html#reversed):274275 ```pycon276 >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]277 >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)278 >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))279 >>> assert standard_way == double_reversed280 >>> standard_way281 [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]282 ```283- Процедуры сортировки используют `<` при сравнении двух объектов. Поэтому легко добавить стандартный порядок сортировки в класс, определив метод [`__lt__()`](https://python-all.ru/3.16/reference/datamodel.html#object.__lt__):284285 ```pycon286 >>> Student.__lt__ = lambda self, other: self.age < other.age287 >>> sorted(student_objects)288 [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]289 ```290291 Однако учтите, что `<` может переключиться на [`__gt__()`](https://python-all.ru/3.16/reference/datamodel.html#object.__gt__), если [`__lt__()`](https://python-all.ru/3.16/reference/datamodel.html#object.__lt__) не реализована (см. [`object.__lt__()`](https://python-all.ru/3.16/reference/datamodel.html#object.__lt__) о механике подробнее). Чтобы избежать неожиданностей, [**PEP 8**](https://python-all.ru/3.16/howto/sorting.html) рекомендует реализовать все шесть методов сравнения. Декоратор [`@~functools.total_ordering`](https://python-all.ru/3.16/library/functools.html#functools.total_ordering) упрощает эту задачу.292- Ключевые функции не обязаны напрямую зависеть от сортируемых объектов. Ключевая функция может также обращаться к внешним ресурсам. Например, если оценки студентов хранятся в словаре, их можно использовать для сортировки отдельного списка имён студентов:293294 ```pycon295 >>> students = ['dave', 'john', 'jane']296 >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}297 >>> sorted(students, key=newgrades.__getitem__)298 ['jane', 'dave', 'john']299 ```300301## Частичная сортировка302303Некоторым приложениям требуется упорядочить только часть данных. Стандартная библиотека предоставляет несколько инструментов, которые выполняют меньшую работу, чем полная сортировка:304305- [`min()`](https://python-all.ru/3.16/library/functions.html#min) и [`max()`](https://python-all.ru/3.16/library/functions.html#max) возвращают наименьшее и наибольшее значения соответственно. Эти функции выполняют один проход по входным данным и почти не требуют дополнительной памяти.306- [`heapq.nsmallest()`](https://python-all.ru/3.16/library/heapq.html#heapq.nsmallest) и [`heapq.nlargest()`](https://python-all.ru/3.16/library/heapq.html#heapq.nlargest) возвращают *n* наименьших и наибольших значений соответственно. Эти функции выполняют один проход по данным, храня в памяти только *n* элементов одновременно. Для значений *n*, малых по сравнению с количеством входных данных, эти функции выполняют гораздо меньше сравнений, чем полная сортировка.307- [`heapq.heappush()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappush) и [`heapq.heappop()`](https://python-all.ru/3.16/library/heapq.html#heapq.heappop) создают и поддерживают частично упорядоченное расположение данных, при котором наименьший элемент находится на позиции `0`. Эти функции подходят для реализации очередей с приоритетом, часто используемых в планировании задач.308