Методы сортировки

Основы сортировки

Выполнить простую сортировку по возрастанию очень легко: просто вызовите функцию 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]

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

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

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

>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['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])   # sort by age
[('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)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Объекты с именованными атрибутами можно создавать с помощью обычного класса, как показано выше, либо они могут быть экземплярами dataclass или именованного кортежа.

Функции модуля operator и частичное применение функций

Описанные выше шаблоны ключевых функций встречаются очень часто, поэтому 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 позволяют выполнять многоуровневую сортировку. Например, сначала сортировать по grade, а затем по age:

>>> 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)]

Модуль functools предоставляет ещё один полезный инструмент для создания ключевых функций. Функция partial() может уменьшить арность функции с несколькими аргументами, сделав её пригодной для использования в качестве ключевой функции.

>>> from functools import partial
>>> from unicodedata import normalize

>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

Сортировка по возрастанию и убыванию

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

>>> 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)]

Стабильность сортировки и сложные сортировки

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

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

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

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

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('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, эффективно выполняет несколько сортировок, поскольку может использовать уже имеющийся порядок элементов в наборе данных.

Декорирование — сортировка — снятие декораций

Этот идиоматический приём называется «декорирование — сортировка — снятие декораций» и состоит из трёх этапов:

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

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

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

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

Включать индекс i в декорированный список нужно не всегда, однако это даёт два преимущества:

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

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

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

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

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

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

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

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

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Разное

• Для сортировки с учётом локали используйте 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__()). Чтобы избежать неожиданностей, PEP 8 рекомендует реализовывать все шесть методов сравнения. Декоратор total_ordering() упрощает эту задачу.

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

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

Частичная сортировка

В некоторых приложениях требуется упорядочить только часть данных. В стандартной библиотеке есть несколько инструментов, требующих меньше ресурсов, чем полная сортировка:

• min() и max() возвращают соответственно наименьшее и наибольшее значения. Эти функции выполняют один проход по входным данным и требуют совсем немного дополнительной памяти.
• heapq.nsmallest() и heapq.nlargest() возвращают соответственно n наименьших и наибольших значений. Эти функции выполняют один проход по данным, сохраняя в памяти не более n элементов одновременно. Если значение n мало по сравнению с количеством входных элементов, эти функции выполняют гораздо меньше сравнений, чем полная сортировка.
• heapq.heappush() и heapq.heappop() создают и поддерживают частично отсортированную структуру данных, в которой наименьший элемент находится в позиции 0. Эти функции подходят для реализации очередей с приоритетами, которые часто используются при планировании задач.