Sorted не работает python

Всё о сортировке в Python: исчерпывающий гайд

Всё о сортировке в 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 проводят множественные сортировки так эффективно, потому что может извлечь пользу из любого порядка, уже присутствующего в наборе данных.

Декорируем-сортируем-раздекорируем

1. Сначала исходный список пополняется новыми значениями, контролирующими порядок сортировки.
2. Затем новый список сортируется.
3. После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.

Вот так можно отсортировать данные учеников по оценке:

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

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

1. Сортировка стабильна — если у двух элементов одинаковый ключ, то их порядок не изменится.
2. У исходных элементов не обязательно должна быть возможность сравнения, так как порядок декорированных кортежей будет определяться максимум по первым двум элементам. Например, исходный список может содержать комплексные числа, которые нельзя сравнивать напрямую.

Ещё эта идиома называется преобразованием Шварца в честь Рэндела Шварца, который популяризировал её среди 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 в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:

• SortedContainers — реализация сортированных типов list , dict и set на чистом Python, по скорости не уступает реализациям на C. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада.
• rbtree — быстрая реализация на C для типов dict и set . Реализация использует структуру данных, известную как красно-чёрное дерево.
• treap — сортированный dict . В реализации используется Декартово дерево, а производительность улучшена с помощью Cython.
• bintrees — несколько реализаций типов dict и set на основе деревьев на C. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей.
• banyan — быстрая реализация dict и set на C.
• skiplistcollections — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов dict и set .
• blist — предоставляет сортированные типы list , dict и set , основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и C.

Прочее

Для сортировки с учётом языка используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения. Параметр reverse всё ещё сохраняет стабильность сортировки. Этот эффект можно сымитировать без параметра, использовав встроенную функцию reversed() дважды:

Чтобы создать стандартный порядок сортировки для класса, просто добавьте реализацию соответствующих методов сравнения:

Для типов, сравнение которых работает обычным образом, рекомендуется определять все 6 операторов. Декоратор классов functools.total_ordering упрощает их реализацию. Функциям-ключам не нужен доступ к внутренним данным сортируемых объектов. Они также могут осуществлять доступ к внешним ресурсам. Например, если оценки ученика хранятся в словаре, их можно использовать для сортировки отдельного списка с именами учеников:

Вас также может заинтересовать статьи:

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник

Python .sort () не работает должным образом

Решая несколько проблем головоломки тихим субботним вечером (ууууууу . нет), я борюсь с sort (). Результаты не совсем то, что я ожидаю. Программа перебирает каждую комбинацию от 100 до 999 и проверяет, является ли продукт палиндомом. Если это так, добавьте в список. Мне нужен список отсортирован: D Вот моя программа:

Очевидно, что индекс 0 больше 1. Есть идеи, что происходит? У меня есть ощущение, что это как-то связано с концевыми / ведущими нулями, но я бросил быстрый взгляд и не вижу проблемы.

Бонусные баллы, если вы знаете, откуда взялась головоломка: P

8 ответов

Вы сортируете строки, а не числа. ‘101101’ потому что ‘1’ . Замените list.append(reversed) на list.append(int(reversed)) , и он будет работать (или использовать другую функцию сортировки).

Оператор сравнения обрабатывает ваш ввод как строки, а не как целые числа. В сравнении строк 2 третья буква лексически больше 1. перевернутый = str (мульт) [:: — 1]

Нет, это сортировка правильно, просто она сортирует лексикографически , и вы хотите сортировку числовой . так что удалите «str ()»

Ваши числа хранятся в виде строк, поэтому Python сортирует их соответствующим образом. Итак: «101x» предшествует «102x» (так же, как «abcd» будет предшествовать «az»).

Нет необходимости конвертировать в int. Mult уже является int и, как вы уже убедились, это палиндром, он будет выглядеть так же, как и полностью измененный, поэтому просто:

Вы сортируете строки, а не числа. Строки сравниваются слева направо.

Ваш список содержит строки, поэтому он сортирует их по алфавиту — попробуйте преобразовать список в целые числа, а затем выполните сортировку.

Сортировка делает свое дело. Если вы намеревались хранить целые числа в списке, воспользуйтесь советом Лукаша. Вы также можете указать сортировку, например, путем создания целых:

Параметр key принимает функцию, которая вычисляет элемент, чтобы занять место объекта списка во всех сравнениях. Целое число будет сравниваться численно, как вы ожидаете.

(Кстати, list — действительно плохое имя переменной, так как вы переопределяете встроенный тип list ()!)

Источник

Проблема сортировки по частоте Python — Sorted () не дает то, что я ожидал

У меня такой код:

Я знаю, как решить начальную идею. Мне просто нужно теоретически понять, почему мой код не работает.

2 ответа

Ваш код не работает, потому что и 11 и 3 (в вашем примере) имеют одинаковое количество; тот же приоритет для сортировки.

Таким образом, 3, 11 является упорядоченной последовательностью, аналогичной 11, 3 или 3, 3, 11, 11 или 3, 11, 3, 11 , поэтому все они правильны, и выбор зависит от способа реализации алгоритма.

Таким образом, вам нужно указать, что ключом порядка является не только количество равных элементов, но и количество равных элементов (с более высокой важностью) и сам элемент (если вы этого хотите). Так что если вы хотите обратный порядок для числа равных элементов и (затем) порядок для значений элементов, вы можете просто использовать:

sorted(numbers, key=lambda i:(-numbers.count(i),i))

Или в равной степени

sorted(numbers, key=lambda i:(numbers.count(i),-i),reverse=True)

Вы могли бы хотеть, чтобы порядок был числом элементов и (тогда) первым появлением элемента, в этом случае вы можете использовать:

sorted(numbers, key=lambda i:(-numbers.count(i),numbers.index(i)))

Или вы можете использовать что-то еще; это зависит от того, как вы хотите отсортировать элементы с одинаковым количеством, но разным значением

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

Проще увидеть, что происходит со строками и без обратного порядка:

Сначала идут все строки длины 2 в исходном порядке, а затем все строки длины 3 также в исходном порядке.

В вашем коде значения с числом 2 в этом порядке 3, 11, 11 и 3. Таким образом, они будут оставаться в этом порядке после сортировки (в обратном порядке, как вы просили, но это будет выглядеть одинаково) ,

Если вы хотите отсортировать по количеству, то по значению (а не по оригинальному порядку) вы должны сделать это явным, используя:

Источник

Сортировка списков в Python

В Python данные можно сортировать с помощью методов sorted() или sort() . В этой статье мы поговорим о том, как работает сортировка списков в Python. Разберем примеры кода для методов sorted() и sort() и посмотрим, чем они отличаются.

Что такое метод sort() в Python?

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

В этом примере у нас есть список чисел, и мы можем использовать метод sort() для сортировки списка в порядке возрастания.

Выполним наш код и получим следующий результат:

Однако если список уже отсортирован, то мы получим None.

Метод sort() может принимать два необязательных аргумента: key и reverse .

Значением key выступает функция, которая будет вызываться для каждого элемента в списке.

От редакции Pythonist. О функциях и их аргументах у нас есть отдельная статья — «Функции и их аргументы в Python 3».

В следующем примере давайте используем функцию len() в качестве значения аргумента key. Таким образом, key=len скажет компьютеру отсортировать список имен по длине, от наименьшего к наибольшему.

Вот, что мы получим:

Аргумент reverse может иметь логическое значение: True (Истина) или False (Ложь).

В следующем примере reverse=True укажет компьютеру отсортировать список в обратном алфавитном порядке.

Марк Лутц «Изучаем Python»

Скачивайте книгу у нас в телеграм

Как использовать метод sorted() в Python

Этот метод превращает итерируемый объект в отсортированный список. Итерируемыми объектами могут быть списки, строки и кортежи.

Одно из ключевых различий между sort() и sorted() заключается в том, что sorted() вернет новый список, а sort() сортирует уже имеющийся.

В следующем примере у нас есть список чисел, который нужно отсортировать в порядке возрастания.

Метод sorted() тоже принимает необязательные аргументы. Они такие же, как и у sort() : key и reverse .

Давайте разберем следующий пример. У нас есть список чисел. Пропишем необязательный аргумент reverse=True . Он укажет компьютеру отсортировать список от наибольшего числа к наименьшему.

Метод sorted() для других типов данных

Еще одно ключевое различие между sorted() и sort() заключается в том, что метод sorted() принимает любые итерируемые объекты (списки, строки, кортежи и т.д.), тогда как метод sort() работает только со списками.

Давайте разобьём строку на отдельные слова с помощью метода split() , а затем используем метод sorted() для сортировки слов по длине от наименьшего к наибольшему.

А теперь давайте чуть изменим наш пример. Добавим необязательный аргумент reverse . Благодаря этому список будет отсортирован в обратном порядке, от самого длинного слова к самому короткому.

Мы также можем использовать метод sorted() и для кортежей.

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

Мы можем использовать метод sorted() для сортировки этих данных по возрасту учащегося. Аргумент key будет иметь значение лямбда-функции, которая сообщает компьютеру о сортировке по возрасту в порядке возрастания.

Лямбда-функция – это анонимная функция. Этот тип функции можно определить с помощью ключевого слова lambda .

Итак, напишем следующую лямбду-функцию, которая будет говорить нашей программе, что отсортировать мы хотим именно по возрасту:

Чтобы получить доступ к значению в кортеже, мы используем квадратные скобки [] и индекс элемента в кортеже, к которому хотим получить доступ. Поскольку в Python отсчет идет с нуля, возраст у нас будет под индексом [1] .

Таким образом, мы получаем следующий код:

Мы можем изменить этот пример. Давайте отсортируем кортежи по названиям музыкальных инструментов. Более того, давайте используем reverse=True для сортировки инструментов в обратном алфавитном порядке.

Заключение

В этой статье мы разобрали, как работает сортировка списков в Python. Узнали, как работать с такими методами, как sort() и sorted() , и в чем их различия.

Метод sort() работает только со списками и сортирует уже имеющийся список. Данный метод ничего не возвращает.

А метод sorted() работает с любыми итерируемыми объектами и возвращает новый отсортированный список. В качестве итерируемых объектов могут выступать списки, строки, кортежи и другие.

У обоих этих методов есть два необязательных аргумента: key и reverse .

Значением аргумента key может быть функция. Она будет вызываться для каждого элемента в списке. По этой функции, собственно, и будет проводиться сортировка.

Значением аргумента reverse может быть True или False .

Надеемся, эта статья была для вас полезна. Успехов в написании кода!

Источник