Сортировка HOW TO

Основные принципы сортировки

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

Старый способ использования Decorate-Sort-Undecorate

Этот приём называется Decorate-Sort-Undecorate из-за трёх его шагов:

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

Например, чтобы отсортировать данные студентов по 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

Многие конструкции, приведённые в этом HOWTO, предполагают Python 2.4 или более поздние версии. До этого не существовало встроенной функции sorted(), а метод list.sort() не принимал ключевых аргументов. Вместо этого все версии Py2.x поддерживали параметр cmp для обработки функций пользовательского сравнения.

В Py3.0 параметр cmp был полностью удалён (как часть более широкой работы по упрощению и унификации языка, устраняя конфликт между богатыми сравнениями и магическим методом __cmp__()).

В Py2.x сортировка позволяла использовать необязательную функцию для выполнения сравнений. Эта функция должна принимать два аргумента для сравнения и возвращать отрицательное значение для меньше-чем, ноль, если они равны, или положительное значение для больше-чем. Например, мы можем сделать следующее:

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) 
[1, 2, 3, 4, 5]

Или вы можете изменить порядок сравнения на:

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) 
[5, 4, 3, 2, 1]

При переносе кода из Python 2.x в 3.x может возникнуть ситуация, когда пользователь предоставляет функцию сравнения, которую нужно преобразовать в функцию ключа. Следующая функция-обёртка делает это легко:

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

Чтобы преобразовать в функцию ключа, просто оберните старую функцию сравнения:

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

В Python 3.2 была добавлена функция functools.cmp_to_key() в модуль functools стандартной библиотеки.

Разное

• Для сортировки с учётом локали используйте 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']