sorting.md

1> **Источник:** https://python-all.ru/3.10/howto/sorting.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# Руководство по сортировке89**Автор**1011Andrew Dalke and Raymond Hettinger1213**Версия**14150.11617Встроенный метод [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort) изменяет список на месте. Также есть встроенная функция [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted), которая создаёт новый отсортированный список из итерируемого объекта.1819В этом документе рассматриваются различные методы сортировки данных с помощью Python.2021## Основы сортировки2223Простая сортировка по возрастанию выполняется очень легко: достаточно вызвать функцию [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted). Она возвращает новый отсортированный список:2425```pycon26>>> sorted([5, 2, 3, 1, 4])27[1, 2, 3, 4, 5]28```2930Также можно использовать метод [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort). Он изменяет список на месте (и возвращает `None`, чтобы избежать путаницы). Обычно он менее удобен, чем [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted), но если исходный список не нужен, он немного эффективнее.3132```pycon33>>> a = [5, 2, 3, 1, 4]34>>> a.sort()35>>> a36[1, 2, 3, 4, 5]37```3839Ещё одно различие: метод [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort) определён только для списков. В то время как функция [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted) принимает любой итерируемый объект.4041```pycon42>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})43[1, 2, 3, 4, 5]44```4546## Ключевые функции4748И [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort), и [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted) имеют параметр *key*, который задаёт функцию (или другой вызываемый объект), вызываемую для каждого элемента списка перед сравнением.4950Например, вот сравнение строк без учёта регистра:5152```pycon53>>> sorted("This is a test string from Andrew".split(), key=str.lower)54['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']55```5657Значением параметра *key* должна быть функция (или другой вызываемый объект), принимающая один аргумент и возвращающая ключ для сортировки. Этот метод быстр, поскольку ключевая функция вызывается ровно один раз для каждой входной записи.5859Часто используется сортировка сложных объектов по некоторым их индексам. Например:6061```pycon62>>> student_tuples = [63...     ('john', 'A', 15),64...     ('jane', 'B', 12),65...     ('dave', 'B', 10),66... ]67>>> sorted(student_tuples, key=lambda student: student[2])   # сортировка по возрасту68[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]69```7071Тот же подход работает для объектов с именованными атрибутами. Например:7273```pycon74>>> class Student:75...     def __init__(self, name, grade, age):76...         self.name = name77...         self.grade = grade78...         self.age = age79...     def __repr__(self):80...         return repr((self.name, self.grade, self.age))8182>>> student_objects = [83...     Student('john', 'A', 15),84...     Student('jane', 'B', 12),85...     Student('dave', 'B', 10),86... ]87>>> sorted(student_objects, key=lambda student: student.age)   # сортировка по возрасту88[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]89```9091## Функции модуля operator9293Рассмотренные выше шаблоны ключевых функций очень распространены, поэтому Python предоставляет вспомогательные функции, чтобы упростить и ускорить создание функций доступа. Модуль [`operator`](https://python-all.ru/3.10/library/operator.html#module-operator) содержит функции [`itemgetter()`](https://python-all.ru/3.10/library/operator.html#operator.itemgetter), [`attrgetter()`](https://python-all.ru/3.10/library/operator.html#operator.attrgetter) и [`methodcaller()`](https://python-all.ru/3.10/library/operator.html#operator.methodcaller).9495Использование этих функций делает приведённые выше примеры проще и быстрее:9697```pycon98>>> from operator import itemgetter, attrgetter99100>>> sorted(student_tuples, key=itemgetter(2))101[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]102103>>> sorted(student_objects, key=attrgetter('age'))104[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]105```106107Функции модуля operator позволяют выполнять многоуровневую сортировку. Например, сортировка сначала по *оценке*, а затем по *возрасту*:108109```pycon110>>> sorted(student_tuples, key=itemgetter(1,2))111[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]112113>>> sorted(student_objects, key=attrgetter('grade', 'age'))114[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]115```116117## По возрастанию и по убыванию118119Обе функции [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort) и [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted) принимают параметр *reverse* с булевым значением. Он используется для указания сортировки по убыванию. Например, чтобы получить данные о студентах в обратном порядке по *возрасту*:120121```pycon122>>> sorted(student_tuples, key=itemgetter(2), reverse=True)123[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]124125>>> sorted(student_objects, key=attrgetter('age'), reverse=True)126[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]127```128129## Стабильность сортировки и сложные сортировки130131Сортировки гарантированно являются [стабильными](https://python-all.ru/3.10/howto/sorting.html). Это означает, что когда несколько записей имеют один и тот же ключ, их исходный порядок сохраняется.132133```pycon134>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]135>>> sorted(data, key=itemgetter(0))136[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]137```138139Обратите внимание, как две записи для *синего* сохраняют исходный порядок, так что `('blue', 1)` гарантированно предшествует `('blue', 2)`.140141Это замечательное свойство позволяет строить сложные сортировки в несколько этапов. Например, чтобы отсортировать данные о студентах сначала по убыванию *оценки*, а затем по возрастанию *возраста*, выполните сортировку по *возрасту* сначала, а затем снова отсортируйте по *оценке*:142143```pycon144>>> s = sorted(student_objects, key=attrgetter('age'))     # сортировка по вторичному ключу145>>> sorted(s, key=attrgetter('grade'), reverse=True)       # теперь сортировка по первичному ключу, по убыванию146[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]147```148149Это можно обобщить в функцию-обёртку, которая принимает список и кортежи из поля и порядка сортировки, чтобы выполнять сортировку в несколько проходов.150151```pycon152>>> def multisort(xs, specs):153...     for key, reverse in reversed(specs):154...         xs.sort(key=attrgetter(key), reverse=reverse)155...     return xs156157>>> multisort(list(student_objects), (('grade', True), ('age', False)))158[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]159```160161Алгоритм [Timsort](https://python-all.ru/3.10/howto/sorting.html), используемый в Python, эффективно выполняет множественные сортировки, поскольку может использовать преимущества любого порядка, уже присутствующего в наборе данных.162163## Старый способ: Decorate-Sort-Undecorate164165Эта идиома называется Decorate-Sort-Undecorate по трём её шагам:166167- Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.168- Затем украшенный список сортируется.169- Наконец, украшения удаляются, создавая список, содержащий только исходные значения в новом порядке.170171Например, чтобы отсортировать данные о студентах по *оценке* с помощью подхода DSU:172173```python174>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]175>>> decorated.sort()176>>> [student for grade, i, student in decorated]               # обратное преобразование177[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]178```179180Эта идиома работает, потому что кортежи сравниваются лексикографически: сравниваются первые элементы; если они одинаковы, то сравниваются вторые, и так далее.181182Не всегда строго необходимо включать индекс *i* в украшенный список, но его включение даёт два преимущества:183184- Сортировка стабильна – если два элемента имеют один и тот же ключ, их порядок сохранится в отсортированном списке.185- Исходные элементы не обязаны быть сравнимыми, поскольку порядок украшенных кортежей будет определяться максимум первыми двумя элементами. Так, например, исходный список может содержать комплексные числа, которые невозможно отсортировать напрямую.186187Другое название этой идиомы – [преобразование Шварца](https://python-all.ru/3.10/howto/sorting.html), по имени Рэндала Л. Шварца, который популяризировал её среди программистов на Perl.188189Теперь, когда сортировка в Python предоставляет ключевые функции, эта техника используется нечасто.190191## Старый способ с параметром *cmp*192193Многие конструкции, описанные в этом руководстве, предполагают Python 2.4 или новее. До этого не было встроенной функции [`sorted()`](https://python-all.ru/3.10/library/functions.html#sorted), а [`list.sort()`](https://python-all.ru/3.10/library/stdtypes.html#list.sort) не принимала именованных аргументов. Вместо этого все версии Py2.x поддерживали параметр *cmp* для обработки пользовательских функций сравнения.194195В Python 3.0 *cmp* параметр был полностью удалён (в рамках более масштабной работы по упрощению и унификации языка, устранению конфликта между расширенными сравнениями и `__cmp__()` магическим методом).196197В Py2.x метод sort принимал необязательную функцию, которую можно вызывать для выполнения сравнений. Эта функция должна была принимать два сравниваемых аргумента и возвращать отрицательное значение, если первый меньше второго, ноль, если они равны, или положительное значение, если первый больше второго. Например:198199```pycon200>>> def numeric_compare(x, y):201...     return x - y202>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) 203[1, 2, 3, 4, 5]204```205206Или можно изменить порядок сравнения с помощью:207208```pycon209>>> def reverse_numeric(x, y):210...     return y - x211>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) 212[5, 4, 3, 2, 1]213```214215При переносе кода с Python 2.x на 3.x может возникнуть ситуация, когда пользователь предоставляет функцию сравнения, и её нужно преобразовать в ключевую функцию. Следующая обёртка упрощает эту задачу:216217```python218def cmp_to_key(mycmp):219    'Convert a cmp= function into a key= function'220    class K:221        def __init__(self, obj, *args):222            self.obj = obj223        def __lt__(self, other):224            return mycmp(self.obj, other.obj) < 0225        def __gt__(self, other):226            return mycmp(self.obj, other.obj) > 0227        def __eq__(self, other):228            return mycmp(self.obj, other.obj) == 0229        def __le__(self, other):230            return mycmp(self.obj, other.obj) <= 0231        def __ge__(self, other):232            return mycmp(self.obj, other.obj) >= 0233        def __ne__(self, other):234            return mycmp(self.obj, other.obj) != 0235    return K236```237238Чтобы преобразовать в ключевую функцию, просто оберните старую функцию сравнения:239240```pycon241>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))242[5, 4, 3, 2, 1]243```244245В Python 3.2 функция [`functools.cmp_to_key()`](https://python-all.ru/3.10/library/functools.html#functools.cmp_to_key) была добавлена в модуль [`functools`](https://python-all.ru/3.10/library/functools.html#module-functools) стандартной библиотеки.246247## Разное248249- Для сортировки с учётом локали используйте [`locale.strxfrm()`](https://python-all.ru/3.10/library/locale.html#locale.strxfrm) в качестве ключевой функции или [`locale.strcoll()`](https://python-all.ru/3.10/library/locale.html#locale.strcoll) в качестве функции сравнения.250- Параметр *reverse* сохраняет стабильность сортировки (так что записи с равными ключами сохраняют исходный порядок). Интересно, что этот эффект можно имитировать без параметра, дважды применив встроенную функцию [`reversed()`](https://python-all.ru/3.10/library/functions.html#reversed):251252  ```pycon253  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]254  >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)255  >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))256  >>> assert standard_way == double_reversed257  >>> standard_way258  [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]259  ```260- Процедуры сортировки используют `<` при сравнении двух объектов. Поэтому легко добавить стандартный порядок сортировки в класс, определив метод `__lt__()`:261262  ```pycon263  >>> Student.__lt__ = lambda self, other: self.age < other.age264  >>> sorted(student_objects)265  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]266  ```267268  Однако обратите внимание, что `<` может вернуться к использованию `__gt__()`, если `__lt__()` не реализован (см. [`object.__lt__()`](https://python-all.ru/3.10/reference/datamodel.html#object.__lt__)).269- Ключевые функции не обязаны напрямую зависеть от сортируемых объектов. Ключевая функция может также обращаться к внешним ресурсам. Например, если оценки студентов хранятся в словаре, их можно использовать для сортировки отдельного списка имён студентов:270271  ```pycon272  >>> students = ['dave', 'john', 'jane']273  >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}274  >>> sorted(students, key=newgrades.__getitem__)275  ['jane', 'dave', 'john']276  ```277