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

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

Простая сортировка по возрастанию очень проста: просто вызовите функцию 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', 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)]

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

Декорация-Сортировка-Декорация

Этот приём называется «Декорация-Сортировка-Декорация» из-за его трёх шагов:

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

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