Sorting Techniques¶

Автор:: Andrew Dalke та Raymond Hettinger

Списки Python мають вбудований метод list.sort(), який змінює список на місці. Існує також вбудована функція sorted(), яка створює новий відсортований список із ітерованого.

У цьому документі ми досліджуємо різні техніки сортування даних за допомогою Python.

Основи сортування¶

Просте сортування за зростанням дуже просте: просто викличте функцію 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.casefold)
['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)]

Objects with named attributes can be made by a regular class as shown above, or they can be instances of dataclass or a named tuple.

Operator Module Functions and Partial Function Evaluation¶

The key function patterns shown above are very common, so Python provides convenience functions to make accessor functions easier and faster. The operator module has itemgetter(), attrgetter(), and a methodcaller() function.

Використовуючи ці функції, наведені вище приклади стають простішими та швидшими:

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

The functools module provides another helpful tool for making key-functions. The partial() function can reduce the arity of a multi-argument function making it suitable for use as a key-function.

>>> from functools import partial
>>> from unicodedata import normalize

>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

Висхідний і спадний¶

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

Ця чудова властивість дозволяє вам створювати складні сорти за допомогою серії кроків сортування. Наприклад, щоб відсортувати дані студента за зменшенням оцінки, а потім за зростанням віку, спочатку виконайте сортування за віком, а потім знову за допомогою оцінки:

>>> 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 після трьох кроків:

По-перше, початковий список прикрашається новими значеннями, які контролюють порядок сортування.
По-друге, оформлений список сортується.
Нарешті, декорації видаляються, створюючи список, який містить лише початкові значення в новому порядку.

Наприклад, щоб відсортувати дані студента за класом за допомогою підходу 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 надає ключові функції, ця техніка не часто потрібна.

Comparison Functions¶

Unlike key functions that return an absolute value for sorting, a comparison function computes the relative ordering for two inputs.

For example, a balance scale compares two samples giving a relative ordering: lighter, equal, or heavier. Likewise, a comparison function such as cmp(a, b) will return a negative value for less-than, zero if the inputs are equal, or a positive value for greater-than.

It is common to encounter comparison functions when translating algorithms from other languages. Also, some libraries provide comparison functions as part of their API. For example, locale.strcoll() is a comparison function.

To accommodate those situations, Python provides functools.cmp_to_key to wrap the comparison function to make it usable as a key function:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Обривки¶

For locale aware sorting, use locale.strxfrm() for a key function or locale.strcoll() for a comparison function. This is necessary because «alphabetical» sort orderings can vary across cultures even if the underlying alphabet is the same.
Параметр 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)]
```
The sort routines use < when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method:
```
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
```
However, note that < can fall back to using __gt__() if __lt__() is not implemented (see object.__lt__() for details on the mechanics). To avoid surprises, PEP 8 recommends that all six comparison methods be implemented. The total_ordering() decorator is provided to make that task easier.
Ключові функції не повинні безпосередньо залежати від об’єктів, які сортуються. Ключова функція також може отримувати доступ до зовнішніх ресурсів. Наприклад, якщо оцінки студентів зберігаються в словнику, їх можна використовувати для сортування окремого списку імен студентів:
```
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
```

Partial Sorts¶

Some applications require only some of the data to be ordered. The standard library provides several tools that do less work than a full sort:

min() and max() return the smallest and largest values, respectively. These functions make a single pass over the input data and require almost no auxiliary memory.
heapq.nsmallest() and heapq.nlargest() return the n smallest and largest values, respectively. These functions make a single pass over the data keeping only n elements in memory at a time. For values of n that are small relative to the number of inputs, these functions make far fewer comparisons than a full sort.
heapq.heappush() and heapq.heappop() create and maintain a partially sorted arrangement of data that keeps the smallest element at position 0. These functions are suitable for implementing priority queues which are commonly used for task scheduling.