Сортировка 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)]

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

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

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

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

Ещё одно название для этого идиома – Schwartzian transform, по имени Рэндолла Л. Шварца, который популяризовал его среди программистов 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 стандартной библиотеки была добавлена функция functools.cmp_to_key().

Разное

• Для сортировки с учётом локали используйте 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__() при сравнении двух объектов. Поэтому легко добавить стандартный порядок сортировки в класс, определив метод __lt__():

  >>> Student.__lt__ = lambda self, other: self.age < other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

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

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