Руководство по сортировке¶Sorting HOW TO

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

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

Ключевые функции¶Key Functions

Оба 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])   # сортировка по возрасту
[('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)   # сортировка по возрасту
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функции модуля operator¶Operator Module Functions

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

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

По возрастанию и по убыванию¶Ascending and Descending

Оба 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)]

Стабильность сортировки и сложные сортировки¶Sort Stability and Complex Sorts

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

>>> 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'))     # сортировка по вторичному ключу
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # теперь сортировка по первичному ключу, по убыванию
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Алгоритм Timsort, используемый в Python, эффективно выполняет множественные сортировки, поскольку может использовать преимущества любого порядка, уже присутствующего в наборе данных.

Старый способ: Decorate-Sort-Undecorate¶The Old Way Using Decorate-Sort-Undecorate

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

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

Например, чтобы отсортировать данные о студентах по оценке с помощью подхода DSU:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # обратное преобразование
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Эта идиома работает, потому что кортежи сравниваются лексикографически: сравниваются первые элементы; если они одинаковы, то сравниваются вторые, и так далее.

Не всегда строго необходимо включать индекс i в украшенный список, но его включение даёт два преимущества:

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

Другое название этой идиомы – преобразование Шварца, по имени Рэндала Л. Шварца, который популяризировал её среди программистов на Perl.

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

Старый способ с параметром cmp¶The Old Way Using the cmp Parameter

Многие конструкции, приведённые в этом HOWTO, предполагают 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.

Разное¶Odd and Ends

• Для сортировки с учётом локали используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения.

• Параметр reverse по-прежнему сохраняет стабильность сортировки (так что записи с равными ключами сохраняют исходный порядок). Интересно, что этот эффект можно воспроизвести без этого параметра, дважды применив встроенную функцию reversed():

  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
  >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))
  

• Алгоритмы сортировки гарантированно используют __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']