sorting.md

1> **Источник:** https://python-all.ru/2.6/howto/sorting.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# Руководство по сортировке89| Автор: | Andrew Dalke and Raymond Hettinger |10| --- | --- |11| Версия: | 0.1 |1213Списки Python имеют встроенный метод `list.sort()`, который изменяет список на месте, и встроенную функцию [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted), которая создаёт новый отсортированный список из итерируемого объекта.1415В этом документе рассматриваются различные методы сортировки данных с помощью Python.1617## Основы сортировки1819Простая сортировка по возрастанию очень легка: достаточно вызвать функцию [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted). Она возвращает новый отсортированный список:2021```python22>>> sorted([5, 2, 3, 1, 4])23[1, 2, 3, 4, 5]24```2526Также можно использовать метод списка `list.sort()`. Он изменяет список на месте (и возвращает *None* во избежание путаницы). Обычно он менее удобен, чем [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted), но если оригинальный список не нужен, он немного эффективнее.2728```python29>>> a = [5, 2, 3, 1, 4]30>>> a.sort()31>>> a32[1, 2, 3, 4, 5]33```3435Ещё одно различие заключается в том, что метод `list.sort()` определён только для списков. В отличие от него, функция [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted) принимает любой итерируемый объект.3637```python38>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})39[1, 2, 3, 4, 5]40```4142## Ключевые функции4344Начиная с Python 2.4, оба – `list.sort()` и [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted) – получили параметр *key*, задающий функцию, которая вызывается для каждого элемента списка перед сравнением.4546Например, вот сравнение строк без учёта регистра:4748```python49>>> sorted("This is a test string from Andrew".split(), key=str.lower)50['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']51```5253Значением параметра *key* должна быть функция, принимающая один аргумент и возвращающая ключ для сортировки. Этот метод эффективен, поскольку функция ключа вызывается ровно один раз для каждой записи на входе.5455Часто используется сортировка сложных объектов по некоторым их индексам. Например:5657```python58>>> student_tuples = [59    ('john', 'A', 15),60    ('jane', 'B', 12),61    ('dave', 'B', 10),62]63>>> sorted(student_tuples, key=lambda student: student[2])   # сортировка по возрасту64[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]65```6667Тот же подход работает для объектов с именованными атрибутами. Например:6869> ```python70> >>> class Student:71>         def __init__(self, name, grade, age):72>             self.name = name73>             self.grade = grade74>             self.age = age75>         def __repr__(self):76>             return repr((self.name, self.grade, self.age))77> ```78>79> ```python80> >>> student_objects = [81>     Student('john', 'A', 15),82>     Student('jane', 'B', 12),83>     Student('dave', 'B', 10),84> ]85> >>> sorted(student_objects, key=lambda student: student.age)   # сортировка по возрасту86> [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]87> ```8889## Функции модуля operator9091Показанные выше шаблоны ключевых функций очень распространены, поэтому Python предоставляет вспомогательные функции, упрощающие и ускоряющие создание функций доступа. Модуль operator содержит [`operator.itemgetter()`](https://python-all.ru/2.6/library/operator.html#operator.itemgetter), [`operator.attrgetter()`](https://python-all.ru/2.6/library/operator.html#operator.attrgetter), а начиная с Python 2.5 – функцию [`operator.methodcaller()`](https://python-all.ru/2.6/library/operator.html#operator.methodcaller).9293Использование этих функций делает приведённые выше примеры проще и быстрее:9495> ```python96> >>> from operator import itemgetter, attrgetter97> ```98>99> ```python100> >>> sorted(student_tuples, key=itemgetter(2))101> [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]102> ```103>104> ```python105> >>> sorted(student_objects, key=attrgetter('age'))106> [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]107> ```108109Функции модуля operator позволяют выполнять многоуровневую сортировку. Например, сортировка сначала по *оценке*, а затем по *возрасту*:110111> ```python112> >>> sorted(student_tuples, key=itemgetter(1,2))113> [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]114> ```115>116> ```python117> >>> sorted(student_objects, key=attrgetter('grade', 'age'))118> [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]119> ```120121## По возрастанию и по убыванию122123Оба – `list.sort()` и [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted) – принимают параметр *reverse* с булевым значением. Он используется для обозначения сортировки по убыванию. Например, чтобы получить данные о студентах в обратном порядке по *возрасту*:124125> ```python126> >>> sorted(student_tuples, key=itemgetter(2), reverse=True)127> [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]128> ```129>130> ```python131> >>> sorted(student_objects, key=attrgetter('age'), reverse=True)132> [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]133> ```134135## Стабильность сортировки и сложные сортировки136137Начиная с Python 2.2, гарантируется, что сортировки являются [устойчивыми](https://python-all.ru/2.6/howto/sorting.html). Это означает, что когда несколько записей имеют одинаковый ключ, их исходный порядок сохраняется.138139```python140>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]141>>> sorted(data, key=itemgetter(0))142[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]143```144145Обратите внимание, как две записи для *blue* сохраняют свой первоначальный порядок, так что `('blue', 1)` гарантированно предшествует `('blue', 2)`.146147Это замечательное свойство позволяет строить сложные сортировки в несколько этапов. Например, чтобы отсортировать данные о студентах сначала по убыванию *оценки*, а затем по возрастанию *возраста*, выполните сортировку по *возрасту* сначала, а затем снова отсортируйте по *оценке*:148149```python150>>> s = sorted(student_objects, key=attrgetter('age'))     # сортировка по вторичному ключу151>>> sorted(s, key=attrgetter('grade'), reverse=True)       # теперь сортировка по первичному ключу, по убыванию152[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]153```154155Алгоритм [Timsort](https://python-all.ru/2.6/howto/sorting.html), используемый в Python, эффективно выполняет множественные сортировки, поскольку может использовать преимущества любого порядка, уже присутствующего в наборе данных.156157## Старый способ: Decorate-Sort-Undecorate158159Эта идиома называется Decorate-Sort-Undecorate по трём её шагам:160161- Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.162- Затем украшенный список сортируется.163- Наконец, украшения удаляются, создавая список, содержащий только исходные значения в новом порядке.164165Например, чтобы отсортировать данные о студентах по *оценке* с помощью подхода DSU:166167```python168>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]169>>> decorated.sort()170>>> [student for grade, i, student in decorated]               # обратное преобразование171[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]172```173174Эта идиома работает, потому что кортежи сравниваются лексикографически: сравниваются первые элементы; если они одинаковы, то сравниваются вторые, и так далее.175176Не всегда строго необходимо включать индекс *i* в украшенный список, но его включение даёт два преимущества:177178- Сортировка стабильна – если два элемента имеют один и тот же ключ, их порядок сохранится в отсортированном списке.179- Исходные элементы не обязаны быть сравнимыми, поскольку порядок украшенных кортежей будет определяться максимум первыми двумя элементами. Так, например, исходный список может содержать комплексные числа, которые невозможно отсортировать напрямую.180181Другое название этой идиомы – [преобразование Шварца](https://python-all.ru/2.6/howto/sorting.html), по имени Рэндала Л. Шварца, который популяризировал её среди программистов на Perl.182183Для больших списков и списков, где информация для сравнения дорого вычисляется, а также для версий Python до 2.4, DSU, вероятно, является самым быстрым способом сортировки списка. Для версий 2.4 и новее ключевые функции предоставляют ту же функциональность.184185## Старый способ с параметром *cmp*186187Многие конструкции, приведённые в этом HOWTO, предполагают Python 2.4 или новее. До этого не было встроенной функции [`sorted()`](https://python-all.ru/2.6/library/functions.html#sorted), а `list.sort()` не принимал именованных аргументов. Вместо этого все версии Py2.x поддерживали параметр *cmp* для обработки пользовательских функций сравнения.188189В Py3.0 параметр *cmp* был полностью удалён (в рамках более широкой работы по упрощению и унификации языка, устранению конфликта между расширенными сравнениями и магическим методом [`__cmp__()`](https://python-all.ru/2.6/reference/datamodel.html#object.__cmp__)).190191В Py2.x метод sort принимал необязательную функцию, которую можно вызывать для выполнения сравнений. Эта функция должна была принимать два сравниваемых аргумента и возвращать отрицательное значение, если первый меньше второго, ноль, если они равны, или положительное значение, если первый больше второго. Например:192193```python194>>> def numeric_compare(x, y):195        return x - y196>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)197[1, 2, 3, 4, 5]198```199200Или можно изменить порядок сравнения с помощью:201202```python203>>> def reverse_numeric(x, y):204        return y - x205>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)206[5, 4, 3, 2, 1]207```208209При переносе кода с Python 2.x на 3.x может возникнуть ситуация, когда пользователь предоставляет функцию сравнения, и её нужно преобразовать в ключевую функцию. Следующая обёртка упрощает эту задачу:210211```python212def cmp_to_key(mycmp):213    'Convert a cmp= function into a key= function'214    class K(object):215        def __init__(self, obj, *args):216            self.obj = obj217        def __lt__(self, other):218            return mycmp(self.obj, other.obj) < 0219        def __gt__(self, other):220            return mycmp(self.obj, other.obj) > 0221        def __eq__(self, other):222            return mycmp(self.obj, other.obj) == 0223        def __le__(self, other):224            return mycmp(self.obj, other.obj) <= 0225        def __ge__(self, other):226            return mycmp(self.obj, other.obj) >= 0227        def __ne__(self, other):228            return mycmp(self.obj, other.obj) != 0229    return K230```231232Чтобы преобразовать в ключевую функцию, просто оберните старую функцию сравнения:233234```python235>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))236[5, 4, 3, 2, 1]237```238239В Python 2.7 функция `functools.cmp_to_key()` была добавлена в модуль functools.240241## Разное242243- Для сортировки с учётом локали используйте [`locale.strxfrm()`](https://python-all.ru/2.6/library/locale.html#locale.strxfrm) в качестве ключевой функции или [`locale.strcoll()`](https://python-all.ru/2.6/library/locale.html#locale.strcoll) в качестве функции сравнения.244- Параметр *reverse* по-прежнему сохраняет стабильность сортировки (т.е. записи с равными ключами сохраняют исходный порядок). Интересно, что такого же эффекта можно достичь без этого параметра, дважды применив встроенную функцию [`reversed()`](https://python-all.ru/2.6/library/functions.html#reversed):245246  ```python247  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]248  >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))249  ```250- Алгоритмы сортировки гарантированно используют [`__lt__()`](https://python-all.ru/2.6/reference/datamodel.html#object.__lt__) при сравнении двух объектов. Таким образом, легко добавить стандартный порядок сортировки для класса, определив метод [`__lt__()`](https://python-all.ru/2.6/reference/datamodel.html#object.__lt__):251252  ```python253  >>> Student.__lt__ = lambda self, other: self.age < other.age254  >>> sorted(student_objects)255  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]256  ```257- Ключевые функции не обязаны напрямую зависеть от сортируемых объектов. Ключевая функция может также обращаться к внешним ресурсам. Например, если оценки студентов хранятся в словаре, их можно использовать для сортировки отдельного списка имён студентов:258259  ```python260  >>> students = ['dave', 'john', 'jane']261  >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}262  >>> sorted(students, key=newgrades.__getitem__)263  ['jane', 'dave', 'john']264  ```265