Sorting HOW TO¶
Python lists have a built-in list.sort() method that modifies the list in-place. There is also a sorted() built-in function that builds a new sorted list from an iterable.
In this document, we explore the various techniques for sorting data using Python.
Sorting Basics¶
A simple ascending sort is very easy: just call the sorted() function. It returns a new sorted list:
You can also use the list.sort() method. It modifies the list in-place (and returns None to avoid confusion). Usually it’s less convenient than sorted() — but if you don’t need the original list, it’s slightly more efficient.
Another difference is that the list.sort() method is only defined for lists. In contrast, the sorted() function accepts any iterable.
Key Functions¶
Both list.sort() and sorted() have a key parameter to specify a function (or other callable) to be called on each list element prior to making comparisons.
For example, here’s a case-insensitive string comparison:
The value of the key parameter should be a function (or other callable) that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.
A common pattern is to sort complex objects using some of the object’s indices as keys. For example:
The same technique works for objects with named attributes. For example:
Operator Module Functions¶
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.
Using those functions, the above examples become simpler and faster:
The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:
Ascending and Descending¶
Both list.sort() and sorted() accept a reverse parameter with a boolean value. This is used to flag descending sorts. For example, to get the student data in reverse age order:
Sort Stability and Complex Sorts¶
Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.
Notice how the two records for blue retain their original order so that (‘blue’, 1) is guaranteed to precede (‘blue’, 2) .
This wonderful property lets you build complex sorts in a series of sorting steps. For example, to sort the student data by descending grade and then ascending age, do the age sort first and then sort again using grade:
This can be abstracted out into a wrapper function that can take a list and tuples of field and order to sort them on multiple passes.
The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.
Decorate-Sort-Undecorate¶
This idiom is called Decorate-Sort-Undecorate after its three steps:
First, the initial list is decorated with new values that control the sort order.
Second, the decorated list is sorted.
Finally, the decorations are removed, creating a list that contains only the initial values in the new order.
For example, to sort the student data by grade using the DSU approach:
This idiom works because tuples are compared lexicographically; the first items are compared; if they are the same then the second items are compared, and so on.
It is not strictly necessary in all cases to include the index i in the decorated list, but including it gives two benefits:
The sort is stable – if two items have the same key, their order will be preserved in the sorted list.
The original items do not have to be comparable because the ordering of the decorated tuples will be determined by at most the first two items. So for example the original list could contain complex numbers which cannot be sorted directly.
Another name for this idiom is Schwartzian transform, after Randal L. Schwartz, who popularized it among Perl programmers.
Now that Python sorting provides key-functions, this technique is not often needed.
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:
Odds and Ends¶
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.
The reverse parameter still maintains sort stability (so that records with equal keys retain the original order). Interestingly, that effect can be simulated without the parameter by using the builtin reversed() function twice:
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:
However, note that < can fall back to using __gt__() if __lt__() is not implemented (see object.__lt__() ).
Key functions need not depend directly on the objects being sorted. A key function can also access external resources. For instance, if the student grades are stored in a dictionary, they can be used to sort a separate list of student names:
Как сортировать массив в питоне
Этот метод по очереди сравнивает каждые два соседних элемента и переставляет их местами, если порядок неправильный. Например, возьмем следующий ряд чисел: 67381. Сначала алгоритм сравнит первые два соседних числа: 6 меньше 7, значит порядок правильный, они остаются на своих местах. Затем следующие два числа – 7 больше 3, значит они меняются местами. Затем он сравнит 7 и 8, и тоже переставит их местами и так далее. После первого прохода по ряду чисел в конце окажется самое большое число – 8. И дальше алгоритм проходит по всем числам снова и будет проходить столько раз, пока каждое число не встанет на свое место – от меньшего к большему.
Вот как это выглядит на языке Питон. Есть список с числами в рандомном порядке, который нужно отсортировать. Сперва сравним первые два числа и поменяем их местами, если порядок неправильный – то есть второе число больше первого. И попросим распечатать получившийся список.
Этот код сравнил 6 с 7, и оставил их на своих местах. Теперь сравним следующие два числа: меняем в коде индексы на 1 и 2. И видим, что он сравнил 3 и 7 и поменял их местами.
Эту операцию нам надо выполнять столько раз, сколько у нас в списке чисел, чтобы каждое из них нашло свое место. Поэтому чтобы не прописывать для каждой пары одну и ту же операцию, мы создаем цикл, равный длине нашего массива минус 1, потому что последнее число в списке не имеет соседа справа, и значит эту операцию сравнения производить не нужно. И просим распечатать получившийся список внутри цикла, чтобы видеть каждый шаг кода.
Этот код постепенно переместил 8 в конец, после одного обхода одно число нашло свое правильное место. Но на этом сортировка не заканчивается. Нам нужно, чтобы каждый элемент массива переместился на свое место – значит нужно сделать столько обходов, сколько у нас чисел. Поэтому мы создаем новый цикл с количеством итераций, равным длине списка. Но здесь мы увидим, что на последнем обходе ничего не поменяется, потому что когда 3 нашла свое место, самый минимальный элемент 1 тоже встал на свое место, значит мы можем отнять 1, чтобы не делать последний обход. Как еще можно оптимизировать этот код? После каждого обхода в конце списка оказывается наибольшее число, и сравнение тех чисел, которые уже нашли свое место, производить не надо. Поэтому мы можем отнять внутри цикла количество обходов, соответствующее итерации цикла – run. Тогда код не будет выполнять лишних операций сравнения.
Давайте теперь превратим наш алгоритм в функцию, которой можно будет передавать любые другие массивы. И протестируем ее на новом списке.
Встроенные методы и функции сортировки
В Python есть встроенные функции и методы сортировки, которые позволяют проделать те же операции одной строчкой кода. В большинстве случаев программисты обходятся ими, но алгоритмы, пример которого мы только что протестировали, важно освоить, чтобы понимать механизм работы этих встроенных функций и методов. И в отдельных случаях, когда данных так много, что встроенные функции и методы сортируют их слишком долго, суметь написать более быструю программу.
Метод .sort() сортирует список и сохраняет его в отсортированном виде. А функция sorted() создает новый отсортированный список без изменения исходного.
Еще одно их отличие в том, что функция sorted работает не только со списками, но и другими объектами. Например, вот что получится, если мы отсортируем строку.
Эта функция возвращает список каждый раз, несмотря на то, какой тип данных был ей передан. В случае со словарями, она возвращает отсортированный список словарных ключей.
По умолчанию сортировка будет происходить по возрастанию, но мы можем передавать функции и методу параметры. За это отвечает параметр reverse. Если мы передадим ему параметр True, сортировка будет происходить по убыванию.
Кроме этого, у sort и sorted есть параметр key, который указывает на функцию сравнения. Например, если мы хотим отсортировать значения без учета регистра текста, можно сделать так:
Внутри параметра key могут находиться не только встроенные функции, но и написанные нами. Они обычно нужны, когда мы хотим отсортировать сложный объект. Например, есть такая проблема: если попытаться отсортировать сложный объект (который состоит, например, из списка списков), сортировка будет выполняться по первому элементу.
Если мы хотим, чтобы сортировка происходила не по первому элементу, мы можем сами создать специальную функцию.
С помощью функций мы можем производить сортировку и внутри словарей – например, отсортировать эти данные по доходу супруги чиновника из ФСБ.
Теперь вы умеете сортировать данные с помощью Python. Тетрадку этого урока можно скачать на нашем GitHub.
Sorting Mini-HOW TO
Python lists have a built-in sort() method that modifies the list in-place and a sorted() built-in function that builds a new sorted list from an iterable.
There are many ways to use them to sort data and there doesn’t appear to be a single, central place in the various manuals describing them, so I’ll do so here.
Sorting Basics
A simple ascending sort is very easy — just call the sorted() function. It returns a new sorted list:
You can also use the list.sort() method of a list. It modifies the list in-place (and returns None to avoid confusion). Usually it’s less convenient than sorted() — but if you don’t need the original list, it’s slightly more efficient.
Another difference is that the list.sort() method is only defined for lists. In contrast, the sorted() function accepts any iterable.
Key Functions
Starting with Python 2.4, both list.sort() and sorted() added a key parameter to specify a function to be called on each list element prior to making comparisons.
For example, here’s a case-insensitive string comparison:
The value of the key parameter should be a function that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.
A common pattern is to sort complex objects using some of the object’s indices as a key. For example:
The same technique works for objects with named attributes. For example:
Operator Module Functions
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 starting in Python 2.6 a methodcaller function.
Using those functions, the above examples become simpler and faster.
The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:
The third function from the operator module, methodcaller is used in the following example in which the weighted grade of each student is shown before sorting on it:
Ascending and Descending
Both list.sort() and sorted() accept a reverse parameter with a boolean value. This is using to flag descending sorts. For example, to get the student data in reverse age order:
Sort Stability and Complex Sorts
Starting with Python 2.2, sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.
Notice how the two records for 'blue' retain their original order so that ('blue', 1) is guaranteed to precede ('blue', 2).
This wonderful property lets you build complex sorts in a series of sorting steps. For example, to sort the student data by descending grade and then ascending age, do the age sort first and then sort again using grade:
The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.
The Old Way Using Decorate-Sort-Undecorate
- First, the initial list is decorated with new values that control the sort order.
- Second, the decorated list is sorted.
- Finally, the decorations are removed, creating a list that contains only the initial values in the new order.
For example, to sort the student data by grade using the DSU approach:
This idiom works because tuples are compared lexicographically; the first items are compared; if they are the same then the second items are compared, and so on.
-
The sort is stable — if two items have the same key, their order will be preserved in the sorted list.
Another name for this idiom is Schwartzian transform, after Randal L. Schwartz, who popularized it among Perl programmers.
For large lists and lists where the comparison information is expensive to calculate, and Python versions before 2.4, DSU is likely to be the fastest way to sort the list. For 2.4 and later, key functions provide the same functionality.
The Old Way Using the cmp Parameter
Many constructs given in this HOWTO assume Python 2.4 or later. Before that, there was no sorted() builtin and list.sort() took no keyword arguments. Instead, all of the Py2.x versions supported a cmp parameter to handle user specified comparison functions.
In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to simplify and unify the language, eliminating the conflict between rich comparisons and the __cmp__ methods).
In Py2.x, sort allowed an optional function which can be called for doing the comparisons. That function should take two arguments to be compared and then return a negative value for less-than, return zero if they are equal, or return a positive value for greater-than. For example, we can do:
Or you can reverse the order of comparison with:
When porting code from Python 2.x to 3.x, the situation can arise when you have the user supplying a comparison function and you need to convert that to a key function. The following wrapper makes that easy to do:
To convert to a key function, just wrap the old comparison function:
In Python 2.7, the cmp_to_key() tool was added to the functools module.
Всё о сортировке в Python: исчерпывающий гайд
Сортировка в Python выполняется функцией sorted() , если это итерируемые объекты, и методом list.sort() , если это список. Рассмотрим подробнее, как это работало в старых версиях и как работает сейчас.
Примечание Вы читаете улучшенную версию некогда выпущенной нами статьи.
Основы сортировки
Для сортировки по возрастанию достаточно вызвать функцию сортировки Python sorted() , которая вернёт новый отсортированный список:
Также можно использовать метод списков list.sort() , который изменяет исходный список (и возвращает None во избежание путаницы). Обычно это не так удобно, как использование sorted() , но если вам не нужен исходный список, то так будет немного эффективнее:
Прим.перев. В Python вернуть None и не вернуть ничего — одно и то же.
Ещё одно отличие заключается в том, что метод list.sort() определён только для списков, в то время как sorted() работает со всеми итерируемыми объектами:
Прим.перев. При итерировании по словарю Python возвращает его ключи. Если вам нужны их значения или пары «ключ-значение», используйте методы dict.values() и dict.items() соответственно.
Рассмотрим основные функции сортировки Python.
Функции-ключи
С версии Python 2.4 у list.sort() и sorted() появился параметр key для указания функции, которая будет вызываться на каждом элементе до сравнения. Вот регистронезависимое сравнение строк:
Значение key должно быть функцией, принимающей один аргумент и возвращающей ключ для сортировки. Работает быстро, потому что функция-ключ вызывается один раз для каждого элемента.
Часто можно встретить код, где сложный объект сортируется по одному из его индексов. Например:
Тот же метод работает для объектов с именованными атрибутами:
Функции модуля operator
Показанные выше примеры функций-ключей встречаются настолько часто, что Python предлагает удобные функции, чтобы сделать всё проще и быстрее. Модуль operator содержит функции itemgetter() , attrgetter() и, начиная с Python 2.6, methodcaller() . С ними всё ещё проще:
Функции operator дают возможность использовать множественные уровни сортировки в Python. Отсортируем учеников сначала по оценке, а затем по возрасту:
Используем функцию methodcaller() для сортировки учеников по взвешенной оценке:
Сортировка по возрастанию и сортировка по убыванию в Python
У list.sort() и sorted() есть параметр reverse , принимающий boolean-значение. Он нужен для обозначения сортировки по убыванию. Отсортируем учеников по убыванию возраста:
Стабильность сортировки и сложные сортировки в Python
Начиная с версии Python 2.2, сортировки гарантированно стабильны: если у нескольких записей есть одинаковые ключи, их порядок останется прежним. Пример:
Обратите внимание, что две записи с ‘blue’ сохранили начальный порядок. Это свойство позволяет составлять сложные сортировки путём постепенных сортировок. Далее мы сортируем данные учеников сначала по возрасту в порядке возрастания, а затем по оценкам в убывающем порядке, чтобы получить данные, отсортированные в первую очередь по оценке и во вторую — по возрасту:
Алгоритмы сортировки Python вроде Timsort проводят множественные сортировки так эффективно, потому что может извлечь пользу из любого порядка, уже присутствующего в наборе данных.
Декорируем-сортируем-раздекорируем
- Сначала исходный список пополняется новыми значениями, контролирующими порядок сортировки.
- Затем новый список сортируется.
- После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.
Вот так можно отсортировать данные учеников по оценке:
Это работает из-за того, что кортежи сравниваются лексикографически, сравниваются первые элементы, а если они совпадают, то сравниваются вторые и так далее.
Не всегда обязательно включать индекс в декорируемый список, но у него есть преимущества:
- Сортировка стабильна — если у двух элементов одинаковый ключ, то их порядок не изменится.
- У исходных элементов не обязательно должна быть возможность сравнения, так как порядок декорированных кортежей будет определяться максимум по первым двум элементам. Например, исходный список может содержать комплексные числа, которые нельзя сравнивать напрямую.
Ещё эта идиома называется преобразованием Шварца в честь Рэндела Шварца, который популяризировал её среди Perl-программистов.
Для больших списков и версий Python ниже 2.4, «декорируем-сортируем-раздекорируем» будет оптимальным способом сортировки. Для версий 2.4+ ту же функциональность предоставляют функции-ключи.
Использование параметра cmp
Все версии Python 2.x поддерживали параметр cmp для обработки пользовательских функций сравнения. В Python 3.0 от этого параметра полностью избавились. В Python 2.x в sort() можно было передать функцию, которая использовалась бы для сравнения элементов. Она должна принимать два аргумента и возвращать отрицательное значение для случая «меньше чем», положительное — для «больше чем» и ноль, если они равны:
Можно сравнивать в обратном порядке:
При портировании кода с версии 2.x на 3.x может возникнуть ситуация, когда нужно преобразовать пользовательскую функцию для сравнения в функцию-ключ. Следующая обёртка упрощает эту задачу:
Чтобы произвести преобразование, оберните старую функцию:
В Python 2.7 функция cmp_to_key() была добавлена в модуль functools.
Поддержание порядка сортировки
В стандартной библиотеке Python нет модулей, аналогичных типам данных C++ вроде set и map . Python делегирует эту задачу сторонним библиотекам, доступным в Python Package Index: они используют различные методы для сохранения типов list , dict и set в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:
-
— реализация сортированных типов list , dict и set на чистом Python, по скорости не уступает реализациям на C. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада. — быстрая реализация на C для типов dict и set . Реализация использует структуру данных, известную как красно-чёрное дерево. — сортированный dict . В реализации используется Декартово дерево, а производительность улучшена с помощью Cython. — несколько реализаций типов dict и set на основе деревьев на C. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей. — быстрая реализация dict и set на C. — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов dict и set . — предоставляет сортированные типы list , dict и set , основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и C.
Прочее
Для сортировки с учётом языка используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения. Параметр reverse всё ещё сохраняет стабильность сортировки. Этот эффект можно сымитировать без параметра, использовав встроенную функцию reversed() дважды:
Чтобы создать стандартный порядок сортировки для класса, просто добавьте реализацию соответствующих методов сравнения:
