Руководство по сортировке¶Sorting HOW TO

Основы сортировки¶Sorting Basics

Простая сортировка по возрастанию выполняется очень легко: достаточно вызвать функцию sorted(). Она возвращает новый отсортированный список:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Также можно использовать метод list.sort(). Он изменяет список на месте (и возвращает None, чтобы избежать путаницы). Обычно он менее удобен, чем sorted(), но если исходный список не нужен, он немного эффективнее.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

Ещё одно различие: метод list.sort() определён только для списков. В то время как функция sorted() принимает любой итерируемый объект.

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Ключевые функции¶Key Functions

И list.sort(), и sorted() имеют параметр key, который задаёт функцию (или другой вызываемый объект), вызываемую для каждого элемента списка перед сравнением.

Например, вот сравнение строк без учёта регистра:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

Значением параметра key должна быть функция (или другой вызываемый объект), принимающая один аргумент и возвращающая ключ для сортировки. Этот метод быстр, поскольку ключевая функция вызывается ровно один раз для каждой входной записи.

Часто используется сортировка сложных объектов по некоторым их индексам. Например:

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # сортировка по возрасту
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Тот же подход работает для объектов с именованными атрибутами. Например:

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # сортировка по возрасту
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функции модуля operator¶Operator Module Functions

Рассмотренные выше шаблоны ключевых функций очень распространены, поэтому Python предоставляет вспомогательные функции, чтобы упростить и ускорить создание функций доступа. Модуль operator содержит функции itemgetter(), attrgetter() и methodcaller().

Использование этих функций делает приведённые выше примеры проще и быстрее:

>>> from operator import itemgetter, attrgetter

>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функции модуля operator позволяют выполнять многоуровневую сортировку. Например, сортировка сначала по оценке, а затем по возрасту:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

По возрастанию и по убыванию¶Ascending and Descending

Обе функции list.sort() и sorted() принимают параметр reverse с булевым значением. Он используется для указания сортировки по убыванию. Например, чтобы получить данные о студентах в обратном порядке по возрасту:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Стабильность сортировки и сложные сортировки¶Sort Stability and Complex Sorts

Сортировки гарантированно являются стабильными. Это означает, что когда несколько записей имеют один и тот же ключ, их исходный порядок сохраняется.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Обратите внимание, как две записи для синего сохраняют исходный порядок, так что ('blue', 1) гарантированно предшествует ('blue', 2).

Это замечательное свойство позволяет строить сложные сортировки в несколько этапов. Например, чтобы отсортировать данные о студентах сначала по убыванию оценки, а затем по возрастанию возраста, выполните сортировку по возрасту сначала, а затем снова отсортируйте по оценке:

>>> s = sorted(student_objects, key=attrgetter('age'))     # сортировка по вторичному ключу
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # теперь сортировка по первичному ключу, по убыванию
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Это можно обобщить в функцию-обёртку, которая принимает список и кортежи из поля и порядка сортировки, чтобы выполнять сортировку в несколько проходов.

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Алгоритм Timsort, используемый в Python, эффективно выполняет множественные сортировки, поскольку может использовать преимущества любого порядка, уже присутствующего в наборе данных.

Декорирование-сортировка-восстановление¶Decorate-Sort-Undecorate

Эта идиома называется Decorate-Sort-Undecorate по трём её шагам:

• Сначала исходный список украшается новыми значениями, которые управляют порядком сортировки.

• Затем украшенный список сортируется.

• Наконец, украшения удаляются, создавая список, содержащий только исходные значения в новом порядке.

Например, чтобы отсортировать данные о студентах по оценке с помощью подхода DSU:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # обратное преобразование
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Эта идиома работает, потому что кортежи сравниваются лексикографически: сравниваются первые элементы; если они одинаковы, то сравниваются вторые, и так далее.

Не всегда строго необходимо включать индекс i в украшенный список, но его включение даёт два преимущества:

• Сортировка стабильна – если два элемента имеют один и тот же ключ, их порядок сохранится в отсортированном списке.

• Исходные элементы не обязаны быть сравнимыми, поскольку порядок украшенных кортежей будет определяться максимум первыми двумя элементами. Так, например, исходный список может содержать комплексные числа, которые невозможно отсортировать напрямую.

Другое название этой идиомы – преобразование Шварца, по имени Рэндала Л. Шварца, который популяризировал её среди программистов на Perl.

Теперь, когда сортировка в Python предоставляет ключевые функции, эта техника используется нечасто.

Функции сравнения¶Comparison Functions

В отличие от ключевых функций, которые возвращают абсолютное значение для сортировки, функция сравнения вычисляет относительный порядок для двух входных значений.

Например, чашечные весы сравнивают два образца, давая относительное упорядочение: легче, равно или тяжелее. Аналогично, функция сравнения, такая как cmp(a, b), вернёт отрицательное значение для «меньше», ноль, если входные значения равны, или положительное значение для «больше».

Часто можно встретить функции сравнения при переводе алгоритмов с других языков. Кроме того, некоторые библиотеки предоставляют функции сравнения как часть своего API. Например, locale.strcoll() – это функция сравнения.

Для таких случаев Python предоставляет functools.cmp_to_key для обёртывания функции сравнения, чтобы сделать её пригодной для использования в качестве ключевой функции:

sorted(words, key=cmp_to_key(strcoll))  # порядок сортировки с учётом локали

Разное¶Odds and Ends

• Для сортировки с учётом локали используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения. Это необходимо, потому что «алфавитный» порядок сортировки может различаться в разных культурах, даже если базовый алфавит один и тот же.

• Параметр reverse сохраняет стабильность сортировки (так что записи с равными ключами сохраняют исходный порядок). Интересно, что этот эффект можно имитировать без параметра, дважды применив встроенную функцию reversed():

  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
  >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
  >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
  >>> assert standard_way == double_reversed
  >>> standard_way
  [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
  

• Процедуры сортировки используют < при сравнении двух объектов. Поэтому легко добавить стандартный порядок сортировки в класс, определив метод __lt__():

  >>> Student.__lt__ = lambda self, other: self.age < other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

  Однако обратите внимание, что < может вернуться к использованию __gt__(), если __lt__() не реализован (см. object.__lt__()).

• Ключевые функции не обязаны напрямую зависеть от сортируемых объектов. Ключевая функция может также обращаться к внешним ресурсам. Например, если оценки студентов хранятся в словаре, их можно использовать для сортировки отдельного списка имён студентов:

  >>> students = ['dave', 'john', 'jane']
  >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
  >>> sorted(students, key=newgrades.__getitem__)
  ['jane', 'dave', 'john']