Сортировка, КАК¶

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

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

Функции операторского модуля¶

Шаблоны ключевых функций, показанные выше, очень распространены, поэтому 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)]

Функции операторского модуля позволяют выполнять сортировку на нескольких уровнях. Например, сортировать по классу, а затем по возрасту:

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

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

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

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

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

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

>>> 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 в оформленный список, но его включение дает два преимущества:

• Сортировка стабильна - если два элемента имеют один и тот же ключ, их порядок в отсортированном списке будет сохранен.

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

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

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

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

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

Например, balance scale сравнивает два образца, задавая относительный порядок: легче, равный или тяжелее. Аналогично, функция сравнения, такая как 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']