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

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

Выполнить простую сортировку по возрастанию очень легко: просто вызовите функцию 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(), min(), max(), heapq.nsmallest() и heapq.nlargest() имеют параметр key, задающий функцию (или другой вызываемый объект), которая вызывается для каждого элемента списка до начала сравнений.

Например, сравнение строк без учёта регистра можно выполнить с помощью str.casefold():

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

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

Способы работы с несортируемыми типами и значениями

При сортировке могут возникать различные проблемы, связанные с типами и значениями. Вот несколько способов, которые могут помочь:

• Перед сортировкой преобразуйте несравнимые типы входных данных в строки:

>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']

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

• Перед сортировкой удалите специальные значения:

>>> from math import isnan
>>> from itertools import filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> sorted(filterfalse(isnan, data))
[1.1, 2.2, 3.3]

Это необходимо, потому что стандарт IEEE-754 гласит: «Каждое NaN должно быть несравнимым со всем, включая само себя».

Аналогичным образом из наборов данных можно удалить и None:

>>> data = [3.3, None, 1.1, 2.2]
>>> sorted(x for x in data if x is not None)
[1.1, 2.2, 3.3]

Это необходимо, потому что None несравнимо с другими типами.

• Перед сортировкой преобразуйте типы отображений в отсортированные списки элементов:

>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]

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

• Перед сортировкой преобразуйте множества в отсортированные списки:

>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]

Это необходимо, потому что элементы множеств не имеют определённого порядка. Например, list({'a', 'b'}) может вернуть ['a', 'b'] или ['b', 'a'].

Разное

• Для сортировки с учётом локали используйте 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 рекомендует реализовать все шесть методов сравнения. Декоратор @~functools.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. Эти функции подходят для реализации очередей с приоритетом, которые часто используются при планировании задач.