Как отсортировать библиотеку в python
Сортировка списка Python
Сортировка данных — одна из самых распространенных задач при работе с Python. Например, вы можете отсортировать список членов команды по именам или список проектов в порядке приоритета.
Python sort() и sorted()
В Python, вы можете сортировать список с помощью встроенного в list.sort() метод или встроенный в sorted() функцию.
Синтаксис sort() и sorted() следующий:
Необязательные ключевые аргументы key и reverse имеют следующее значение:
Элементы списка сравниваются с помощью оператора «меньше чем» ( ) и сортируются в порядке возрастания. Оператор не поддерживает сравнение строки с целым числом, поэтому, если у вас есть список, содержащий строки и целые числа, операция сортировки завершится ошибкой.
В следующем примере показано, как отсортировать список строк в алфавитном порядке:
Если вы хотите сохранить исходный список без изменений, используйте функцию sorted() :
Чтобы отсортировать список в обратном (по убыванию) порядке, установите reverse аргумент в True :
Сортировка с функцией
Аргумент key принимает функцию и позволяет выполнять более сложные операции сортировки.
Самый простой пример — отсортировать элементы по их длине:
Мы используем функцию len() чтобы вернуть количество символов в строке, которая используется в качестве компаратора:
Вы также можете создать пользовательскую функцию и использовать ее в качестве key аргумента для сравнения. Вот пример, показывающий, как отсортировать список целых чисел по сумме их цифр:
Другой пример — использование ключевого аргумента для сортировки сложного списка, такого как список кортежей:
Мы используем анонимную (лямбда) функцию, которая возвращает первый элемент кортежа. Список отсортирован по значению, возвращаемому функцией:
Тот же подход можно использовать для сортировки списка словарей:
Функция itemgetter извлекает значение symbol ключа:
Выводы
Если у вас есть какие-либо вопросы или отзывы, не стесняйтесь оставлять комментарии.
Поводом опубликовать пост стало то, что при детальном изучении списков (массивов) в Python я не смог найти в сети ни одного простого описания метода сортировки элементов с использованием ключа: list.sort(key=. ).
Может быть, конечно, это мне так не повезло и я долго понимаю простые для всех вещи, однако я думаю, что приведенная ниже информация будет весьма полезна таким же начинающим питонистам, как и я сам.
Итак, что мы имеем. Предположим, у нас есть список, который мы бы хотели отсортировать — и состоит он из трех строк разной длины в определенной последовательности:
sortList = [‘a’, ‘сс’, ‘bbb’]
то получим на выходе:
Для изменения принципа сортировки используется ключевое слово key, которое стало доступным начиная с версии Python 2.4.
Предположим, нам хотелось бы отсортировать наш список двумя способами: 1. в алфавитном порядке; 2. по длине строки. Первый способ, впрочем, уже работает как сортировка по умолчанию, однако мы можем добиться таких же результатов и с помощью параметра key:
sortList = [‘a’, ‘cc’, ‘bbb’]
# Создаем «внешнюю» функцию, которая будет сортировать список в алфавитном порядке:
def sortByAlphabet(inputStr):
return inputStr[0] # Ключом является первый символ в каждой строке, сортируем по нему
# Вторая функция, сортирующая список по длине строки:
def sortByLength(inputStr):
return len(inputStr) # Ключом является длина каждой строки, сортируем по длине
print u’Исходный список: ‘, sortList # >>> [‘a’, ‘cc’, ‘bbb’]
sortList.sort(key=sortByAlphabet) # Каждый элемент массива передается в качестве параметра функции
print u’Отсортировано в алфавитном порядке: ‘, sortList # >>> [‘a’, ‘bbb’, ‘cc’]
sortList.sort(key=sortByLength) # Каждый элемент массива передается в качестве параметра функции
print u’Отсортировано по длине строки: ‘, sortList # >>> [‘a’, ‘cc’, ‘bbb’]
# Теперь отсортируем по длине строки, но в обратном порядке:
sortList.sort(key=sortByLength, reverse=True) # В обратном порядке
print u’Отсортировано по длине строки, в обратном порядке: ‘, sortList # >>> [‘bbb’, ‘cc’, ‘a’]
— либо такой же вариант, но с параметром key (аналогично описанному выше):
newList = sorted(sortList, key=sortByLength)
Sorting HOW TO¶
Andrew Dalke and Raymond Hettinger
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:
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¶
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.
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.
The Old Way Using 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.
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__() magic method).
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 3.2, the functools.cmp_to_key() function was added to the functools module in the standard library.
Odd and Ends¶
For locale aware sorting, use locale.strxfrm() for a key function or locale.strcoll() for a comparison function.
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 are guaranteed to use __lt__() when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method:
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:
6 примеров сортировки в Python с помощью функции sorted
Общей идиомой в программировании является сортировка списка. Python делает эту задачу очень простой благодаря встроенной функции sorted() которая принимает итерируемый тип и возвращает отсортированный список:
1. Стандартная сортировка
Обратите внимание на то, что функция sorted() возвращает список каждый раз, несмотря на то, какой тип был передан. В случае со словарями, она возвращает отсортированный список словарных ключей.
2. Сортировка сложных структур с использованием ключа
Это нормально работать с вещами, у которых по природе есть определенный порядок, вроде чисел или строк, но что делать с более сложными структурами? Здесь функция sorted() демонстрирует свое великолепие. Функция sorted() принимает ключ в качестве опционально названного параметра. Этот ключ должен быть, сам по себе, функцией, которая принимает один параметр, которая затем используется функцией sorted(), для определения значения в целях дальнейшей сортировки. Давайте взглянем на пример. Скажем, у нас есть класс Person с такими атрибутами как имя и возраст:
(Функция __repr__ является специальной функцией, которая используется для переопределения того, как объект будет представлен в интерпретаторе Python)
Причина, по которой я определил функцию – это выделение порядка сортировки. По умолчанию, представление определенных пользователем объектов выглядит примерно так: “ ”. Если оставить все как есть, то отличать различные экземпляры в будущих примерах будет несколько затруднительно для нас.
Давайте сделаем список людей:
Сама по себе функция sorted() не знает, что делать со списком людей:
Однако, мы можем указать функции sorted(), какой атрибут сортировать, указав используемый ключ. Давайте определим это в следующем примере:
Функция ключа должна принять один аргумент и выдать значение, на котором базируется сортировка. Функция sorted() должна вызвать функцию key в каждом элементе используемой итерируемой, и использовать значение выдачи при сортировке списка.
Обратите внимание на то, что мы передаем ссылку на саму функцию, не вызывая ее и передаем ссылку к её возвращаемому значению. Это очень важный момент. Помните, sorted() будет использовать функцию key, вызывая её в каждом элементе итерируемой.
Давайте взглянем на еще один код, на этот раз определяем возраст как значение для сортировки:
3. Обратная сортировка
Функция sorted() намного упрощает сортировку в обратном порядке. Функция принимает опциональный параметр под названием reverse, который действует по строгой логике.
4. Сортировка с использованием функции attrgetter
В этот раз, возвращаемый список отсортирован по возрасту, как мы и ожидали. Фактически, сортировка по определенному атрибуту объекта это простая задача Python, которую может выполнить стандартная библиотека, благодаря функции, которая может генерировать функции ключей для вас:
Результат вызова attrgetter() – это функция, схожая с предыдущими двумя, которые мы только что рассмотрели. Мы определяем имя атрибута для выборки, после чего attrgetter генерирует функцию, которая принимает объект и возвращает определенный атрибут из этого объекта.
Таким образом, attrgetter(name) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byName_key():
Функция attrgetter(age) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byAge_key():
5. Предварительное использование key в функции сортировки
До сих пор нашими ключевыми функциями были простые считыватели атрибутов, но они также могут вычислять значения для сортировки. Давайте взглянем на еще один пример. На этот раз мы определим класс Snake:
У нашей змеи есть имя, toxicity (токсичность, мерило того, насколько токсичен её яд) и agression (представленная в виде числа от 0 до 1, которое указывает на вероятность того, что змея нападет).
Надежный сайт по продвижению doctorsmm предлагает купить подписчиков на свой Телеграмм канал по очень выгодным и притягательным ценам от 51 рубля за сотню аккаунтов. Кроме того, Вы сможете подобрать наиболее оптимальную для Вашего сообщества скорость поступления, которая доходит до 1000 единиц в сутки.
Теперь предположим, что мы можем подсчитать, насколько опасная змея, основываясь на показателях токсичности и агрессивности, и можем отсортировать список змей по степени их опасности:
Змеи отсортированы в ожидаемом нами порядке (несмотря на то, что гремучая змея (rattlesnake) более ядовита, чем кобра (kingCobra), уровень агрессивности кобры делает её более опасной).
6. Случайная сортировка
Ключи не обязаны иметь какую-либо связь с сортируемыми элементами (однако, это не самый продуктивный способ сортировать что-либо). Мы можем создать случайный порядок со следующим ключом:
Функция random() – это часть стандартной библиотеки random, которая выдает числа в случайном порядке от 0 до 1. Сортировка с использованием данного ключа выдает, кто бы мог подумать, случайный порядок:
В данной статье мы рассмотрели то, как Python создает отсортированные списки (и другие итерируемые) и то, насколько это просто. По умолчанию, функция sorted() возвращает список, содержимое которого упорядоченно в естественном порядке (что, в общем, именно то что мы ожидаем от чисел и строк). Желающие углубиться в то, как работает функция sorted() могут обратиться к документации Python.
Виды алгоритмов сортировки в Python
В одной из прошлых статей я рассматривал списки в Python, а также затронул их сортировку. Теперь давайте разберем эту тему более подробно: изучим виды алгоритмов сортировки и сравним их скорость на примере сортировки чисел в порядке возрастания.
Встроенные методы сортировки в Python
Стандартный метод сортировки списка по возрастанию – sort(). Пример использования:
Метод sorted() создает новый отсортированный список, не изменяя исходный. Пример использования:
Если нам нужна сортировка от большего числа к меньшему, то установим флаг reverse=True. Примеры:
Но будет полезно знать и другие виды сортировки, так как не всегда встроенные методы будут подходить под все ваши задачи.
Пузырьковая сортировка
Алгоритм попарно сравнивает элементы списка, меняя их местами, если это требуется. Он не так эффективен, если нам нужно сделать только один обмен в списке, так как данный алгоритм при достижении конца списка будет повторять процесс заново. Чтобы алгоритм не выполнялся бесконечно, мы вводим переменную, которая поменяет свое значение с True на False, если после запуска алгоритма список не изменился.
Сравниваются первые два элемента. Если первый элемент больше, то они меняются местами. Далее происходит все то же самое, но со следующими элементами до последней пары элементов в списке.
Пример пузырьковой сортировки:
Сортировка вставками
Алгоритм делит список на две части, вставляя элементы на их правильные места во вторую часть списка, убирая их из первой.
Если второй элемент больше первого, то оставляем его на своем месте. Если он меньше, то вставляем его на второе место, оставив первый элемент на первом месте. Далее перемещаем большие элементы во второй части списка вверх, пока не встретим элемент меньше первого или не дойдем до конца списка.
Пример сортировки вставками:
Сортировка выборкой
Как и сортировка вставками, этот алгоритм в Python делит список на две части: основную и отсортированную. Наименьший элемент удаляется из основной части и переходит в отсортированную.
Саму отсортированную часть можно и не создавать, обычно используют крайнюю часть списка. И когда находится наименьший элемент списка, то переносим его на первое место, вставляя первый элемент на прошлое порядковое место наименьшего. Далее делаем все то же самое, но со следующим элементом, пока не достигнем конца списка.
Пример сортировки выборкой:
Пирамидальная сортировка
Этот алгоритм, как и сортировки вставками или выборкой, делит список на две части. Алгоритм преобразует вторую часть списка в бинарное дерево для эффективного определения самого большого элемента.
Преобразуем список в бинарное дерево, где самый большой элемент является вершиной дерева, и помещаем этот элемент в конец списка. После перестраиваем дерево и помещаем новый наибольший элемент перед последним элементом в списке. Повторяем этот алгоритм, пока все вершины дерева не будут удалены.
Хоть алгоритм и кажется сложным, он значительно быстрее остальных, что особенно заметно при обработке больших списков.
Пример пирамидальной сортировки:
Сортировка слиянием
Алгоритм разделяет список на две части, каждую из них он разделяет еще на две и так далее, пока не останутся отдельные единичные элементы. Далее соседние элементы сортируются парами. Затем эти пары объединяются и сортируются с другими парами, пока не обработаются все элементы в списке.
Пример сортировки слиянием:
Быстрая сортировка в Python
Один из самых популярных алгоритмов при сортировке списков. При правильном использовании он не требует много памяти и выполняется очень быстро.
Алгоритм разделяет список на две равные части, принимая псевдослучайный элемент и используя его в качестве опоры, то есть центра деления. Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше опоры – вправо. Этот процесс повторяется для списка слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементу списка.
Пример быстрой сортировки:
Скорость работы алгоритмов
Сортировка слиянием почти в два раза медленнее, чем быстрая сортировка. Сортировка выборкой выполняет больше сравнений, чем сортировка вставками, но выполняется немного быстрее.
Пузырьковая сортировка не подойдет для практического применения, так как она является самой медленной из всех. Но знать данный алгоритм будет полезно тем, кто хочет полностью изучить тему алгоритмов сортировки списков в Python.
Мы изучили виды сортировки списков в Python и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!