Как сортировать данные

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

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

Функции модуля 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)]

Возрастание и убывание

И 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__()).

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

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