Сортировка. Руководство

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

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

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

Используемый в 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

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

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

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

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