Техники сортировки

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

Простую сортировку по возрастанию выполнить очень легко: достаточно вызвать функцию 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 позволяют выполнять сортировку по нескольким уровням. Например, сначала по оценке, а затем по возрасту:

>>> 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 со значением типа bool. Он указывает на сортировку по убыванию. Например, чтобы получить данные об учениках, отсортированные по возрасту в обратном порядке:

>>> 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', 1) гарантированно располагается перед ('blue', 2).

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

>>> 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, выполняет несколько сортировок эффективно, поскольку может использовать уже существующий порядок элементов в наборе данных.

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

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

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

Например, чтобы отсортировать данные об учениках по оценке с помощью подхода 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. Эти функции подходят для реализации очередей с приоритетом, которые часто используются при планировании задач.