Всё о сортировке в Python: исчерпывающий гайд
Сортировка в Python выполняется с помощью sorted() и list.sort(). Разбираем на примерах, как это работает.
Сортировка в Python выполняется функцией sorted() , если это итерируемые объекты, и методом list.sort() , если это список. Рассмотрим подробнее, как это работало в старых версиях и как работает сейчас.
Примечание Вы читаете улучшенную версию некогда выпущенной нами статьи.
Основы сортировки
Так как отсортировать список Python? Для сортировки по возрастанию достаточно вызвать функцию сортировки Python sorted() , которая вернёт новый отсортированный список:
>>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] Для сортировки списка Python также можно использовать метод списков list.sort() , который изменяет исходный список (и возвращает None во избежание путаницы). Обычно Python sort list не так удобен, как использование sorted() , но если вам не нужен исходный список, то так будет немного эффективнее:
>>> a = [5, 2, 3, 1, 4] >>> a.sort() >>> a [1, 2, 3, 4, 5] Прим.перев. В Python вернуть None и не вернуть ничего — одно и то же.
Ещё одно отличие заключается в том, что метод list.sort() определён только для списков, в то время как функция sorted Python работает со всеми итерируемыми объектами. Грубо говоря, функция sort Python сортирует список и сохраняет его в отсортированном виде, в то время как функция sorted Питон создаёт новый отсортированный список без изменения исходного.
>>> sorted() [1, 2, 3, 4, 5] Прим.перев. При итерировании по словарю Python возвращает его ключи. Если вам нужны их значения или пары «ключ-значение», используйте методы dict.values() и dict.items() соответственно.
Рассмотрим основные функции сортировки Python.
Функции-ключи
С версии Python 2.4 у 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)) def weighted_grade(self): return 'CBA'.index(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
Показанные выше примеры функций-ключей встречаются настолько часто, что Python предлагает удобные функции, чтобы сделать всё проще и быстрее. Модуль operator содержит функции itemgetter() , attrgetter() и, начиная с Python 2.6, methodcaller() . С ними всё ещё проще:
>>> from operator import itemgetter, attrgetter, methodcaller >>> 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 дают возможность использовать множественные уровни сортировки массива Python. Отсортируем учеников сначала по оценке, а затем по возрасту:
>>> 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)] Используем функцию methodcaller() для сортировки учеников по взвешенной оценке:
>>> [(student.name, student.weighted_grade()) for student in student_objects] [('john', 0.13333333333333333), ('jane', 0.08333333333333333), ('dave', 0.1)] >>> sorted(student_objects, key=methodcaller('weighted_grade')) [('jane', 'B', 12), ('dave', 'B', 10), ('john', 'A', 15)] Сортировка по возрастанию и сортировка по убыванию в Python
list.sort() и sorted() есть параметр reverse , принимающий boolean-значение. Он нужен для обозначения сортировки по убыванию. Отсортируем учеников по убыванию возраста:
>>> 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)] Стабильность сортировки и сложные сортировки в Python
Начиная с версии Python 2.2, сортировки гарантированно стабильны: если у нескольких записей есть одинаковые ключи, их порядок останется прежним. Пример:
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> sorted(data, key=itemgetter(0)) [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)] Обратите внимание, что две записи с ‘blue’ сохранили начальный порядок. Это свойство позволяет составлять сложные сортировки путём постепенных сортировок. Далее мы сортируем данные учеников сначала по возрасту в порядке возрастания, а затем по оценкам в убывающем порядке, чтобы получить данные, отсортированные в первую очередь по оценке и во вторую — по возрасту:
>>> s = sorted(student_objects, key=attrgetter('age')) # сортируем по вторичному ключу >>> sorted(s, key=attrgetter('grade'), reverse=True) # по первичному [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] Алгоритмы сортировки Python вроде Timsort проводят множественные сортировки так эффективно, потому что может извлечь пользу из любого порядка, уже присутствующего в наборе данных.
Декорируем-сортируем-раздекорируем
- Сначала исходный список пополняется новыми значениями, контролирующими порядок сортировки.
- Затем новый список сортируется.
- После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.
Вот так можно отсортировать данные учеников по оценке:
>>> 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)] Это работает из-за того, что кортежи сравниваются лексикографически, сравниваются первые элементы, а если они совпадают, то сравниваются вторые и так далее.
Не всегда обязательно включать индекс в декорируемый список, но у него есть преимущества:
- Сортировка стабильна — если у двух элементов одинаковый ключ, то их порядок не изменится.
- У исходных элементов не обязательно должна быть возможность сравнения, так как порядок декорированных кортежей будет определяться максимум по первым двум элементам. Например, исходный список может содержать комплексные числа, которые нельзя сравнивать напрямую.
Ещё эта идиома называется преобразованием Шварца в честь Рэндела Шварца, который популяризировал её среди Perl-программистов.
Для больших списков и версий Python ниже 2.4, «декорируем-сортируем-раздекорируем» будет оптимальным способом сортировки. Для версий 2.4+ ту же функциональность предоставляют функции-ключи.
Использование параметра cmp
Все версии Python 2.x поддерживали параметр cmp для обработки пользовательских функций сравнения. В Python 3.0 от этого параметра полностью избавились. В Python 2.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] При портировании кода с версии 2.x на 3.x может возникнуть ситуация, когда нужно преобразовать пользовательскую функцию для сравнения в функцию-ключ. Следующая обёртка упрощает эту задачу по Python:
def cmp_to_key(mycmp): 'Перевести cmp=функция в key=функция' class K(object): 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 __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 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() дважды:
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data)))) Чтобы создать стандартный порядок сортировки для класса, просто добавьте реализацию соответствующих методов сравнения:
>>> Student.__eq__ = lambda self, other: self.age == other.age >>> Student.__ne__ = lambda self, other: self.age != other.age >>> Student.__lt__ = lambda self, other: self.age < other.age >>> Student.__le__ = lambda self, other: self.age >> Student.__gt__ = lambda self, other: self.age > other.age >>> Student.__ge__ = lambda self, other: self.age >= other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] Для типов, сравнение которых работает обычным образом, рекомендуется определять все 6 операторов. Декоратор классов functools.total_ordering упрощает их реализацию. Функциям-ключам не нужен доступ к внутренним данным сортируемых объектов. Они также могут осуществлять доступ к внешним ресурсам. Например, если оценки ученика хранятся в словаре, их можно использовать для сортировки отдельного списка с именами учеников:
>>> students = ['dave', 'john', 'jane'] >>> newgrades = >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john'] Надеемся, теория по Python list sort и соответствующие задачи по Питону с разбором были для вас полезны. Вас также может заинтересовать статьи:
- Хочу научиться программировать на Python. С чего начать?
- Хочу научиться программировать на Python: инструкция для продолжающих
Сортировка списков в Python
В Python данные можно сортировать с помощью методов sorted() или sort() . В этой статье мы поговорим о том, как работает сортировка списков в Python. Разберем примеры кода для методов sorted() и sort() и посмотрим, чем они отличаются.
Что такое метод sort() в Python?
Этот метод берет список и сортирует его. То есть на выходе мы получаем тот же список, только отсортированный. Этот метод не возвращает никакого значения.
В этом примере у нас есть список чисел, и мы можем использовать метод sort() для сортировки списка в порядке возрастания.
my_list = [67, 2, 999, 1, 15] # Выводим неупорядоченный список: print("Unordered list: ", my_list) # Сортировка списка my_list.sort() # Выводим упорядоченный список print("Ordered list: ", my_list)
Выполним наш код и получим следующий результат:
Unordered list: [67, 2, 999, 1, 15] Ordered list: [1, 2, 15, 67, 999]
Однако если список уже отсортирован, то мы получим None.
my_list = [6, 7, 8, 9, 10] # Это строка вернет None, потому что список уже отсортирован print(my_list.sort())
Метод sort() может принимать два необязательных аргумента: key и reverse .
Значением key выступает функция, которая будет вызываться для каждого элемента в списке.
От редакции Pythonist. О функциях и их аргументах у нас есть отдельная статья — «Функции и их аргументы в Python 3».
В следующем примере давайте используем функцию len() в качестве значения аргумента key. Таким образом, key=len скажет компьютеру отсортировать список имен по длине, от наименьшего к наибольшему.
names = ["Jessica", "Ben", "Carl", "Jackie", "Wendy"] print("Unsorted: ", names) names.sort(key=len) print("Sorted: ", names)
Вот, что мы получим:
Unsorted: ['Jessica', 'Ben', 'Carl', 'Jackie', 'Wendy'] Sorted: ['Ben', 'Carl', 'Wendy', 'Jackie', 'Jessica']
Аргумент reverse может иметь логическое значение: True (Истина) или False (Ложь).
В следующем примере reverse=True укажет компьютеру отсортировать список в обратном алфавитном порядке.
names = ["Jessica", "Ben", "Carl", "Jackie", "Wendy"] print("Unsorted: ", names) names.sort(reverse=True) print("Sorted: ", names) # Результат: # Unsorted: ['Jessica', 'Ben', 'Carl', 'Jackie', 'Wendy'] # Sorted: ['Wendy', 'Jessica', 'Jackie', 'Carl', 'Ben']
[python_ad_block]
Как использовать метод sorted() в Python
Этот метод превращает итерируемый объект в отсортированный список. Итерируемыми объектами могут быть списки, строки и кортежи.
Одно из ключевых различий между sort() и sorted() заключается в том, что sorted() вернет новый список, а sort() сортирует уже имеющийся.
В следующем примере у нас есть список чисел, который нужно отсортировать в порядке возрастания.
sorted_numbers = sorted([77, 22, 9, -6, 4000]) print("Sorted in ascending order: ", sorted_numbers) # Результат: # Sorted in ascending order: [-6, 9, 22, 77, 4000]
Метод sorted() тоже принимает необязательные аргументы. Они такие же, как и у sort() : key и reverse .
Давайте разберем следующий пример. У нас есть список чисел. Пропишем необязательный аргумент reverse=True . Он укажет компьютеру отсортировать список от наибольшего числа к наименьшему.
sorted_numbers = sorted([77, 22, 9, -6, 4000], reverse=True) print("Sorted in descending order: ", sorted_numbers) # Результат: # Sorted in descending order: [4000, 77, 22, 9, -6]
Метод sorted() для других типов данных
Еще одно ключевое различие между sorted() и sort() заключается в том, что метод sorted() принимает любые итерируемые объекты (списки, строки, кортежи и т.д.), тогда как метод sort() работает только со списками.
Давайте разобьём строку на отдельные слова с помощью метода split() , а затем используем метод sorted() для сортировки слов по длине от наименьшего к наибольшему.
my_sentence = "Jessica found a dollar on the ground" # Вывод оригинального предложения: print("Original sentence: ", my_sentence) # Вывод отсортированного списка слов: print(sorted(my_sentence.split(), key=len)) # Результат: # Original sentence: Jessica found a dollar on the ground # ['a', 'on', 'the', 'found', 'dollar', 'ground', 'Jessica']
А теперь давайте чуть изменим наш пример. Добавим необязательный аргумент reverse . Благодаря этому список будет отсортирован в обратном порядке, от самого длинного слова к самому короткому.
my_sentence = "Jessica found a dollar on the ground" print("Original sentence: ", my_sentence) print(sorted(my_sentence.split(), key=len, reverse=True)) # Результат: # Original sentence: Jessica found a dollar on the ground # ['Jessica', 'dollar', 'ground', 'found', 'the', 'on', 'a']
Мы также можем использовать метод sorted() и для кортежей.
В этом примере у нас есть набор кортежей, которые представляют имя, возраст и музыкальный инструмент учащихся какой-то группы.
band_students = [ ('Danny', 17, 'Trombone'), ('Mary', 14, 'Flute'), ('Josh', 15, 'Percussion') ]
Мы можем использовать метод sorted() для сортировки этих данных по возрасту учащегося. Аргумент key будет иметь значение лямбда-функции, которая сообщает компьютеру о сортировке по возрасту в порядке возрастания.
Лямбда-функция – это анонимная функция. Этот тип функции можно определить с помощью ключевого слова lambda .
Итак, напишем следующую лямбду-функцию, которая будет говорить нашей программе, что отсортировать мы хотим именно по возрасту:
lambda student: student[1]
Чтобы получить доступ к значению в кортеже, мы используем квадратные скобки [] и индекс элемента в кортеже, к которому хотим получить доступ. Поскольку в Python отсчет идет с нуля, возраст у нас будет под индексом [1] .
Таким образом, мы получаем следующий код:
band_students = [ ('Danny', 17, 'Trombone'), ('Mary', 14, 'Flute'), ('Josh', 15, 'Percussion') ] print(sorted(band_students, key=lambda student: student[1])) # Результат: # [('Mary', 14, 'Flute'), ('Josh', 15, 'Percussion'), ('Danny', 17, 'Trombone')]
Мы можем изменить этот пример. Давайте отсортируем кортежи по названиям музыкальных инструментов. Более того, давайте используем reverse=True для сортировки инструментов в обратном алфавитном порядке.
band_students = [ ('Danny', 17, 'Trombone'), ('Mary', 14, 'Flute'), ('Josh', 15, 'Percussion') ] print(sorted(band_students, key=lambda student: student[2], reverse=True)) # Результат: # [('Danny', 17, 'Trombone'), ('Josh', 15, 'Percussion'), ('Mary', 14, 'Flute')]
Заключение
В этой статье мы разобрали, как работает сортировка списков в Python. Узнали, как работать с такими методами, как sort() и sorted() , и в чем их различия.
Метод sort() работает только со списками и сортирует уже имеющийся список. Данный метод ничего не возвращает.
А метод sorted() работает с любыми итерируемыми объектами и возвращает новый отсортированный список. В качестве итерируемых объектов могут выступать списки, строки, кортежи и другие.
У обоих этих методов есть два необязательных аргумента: key и reverse .
Значением аргумента key может быть функция. Она будет вызываться для каждого элемента в списке. По этой функции, собственно, и будет проводиться сортировка.
Значением аргумента reverse может быть True или False .
Надеемся, эта статья была для вас полезна. Успехов в написании кода!
Алгоритмы сортировки в Python
Иногда данные, которые мы храним или извлекаем в приложении, могут находится в беспорядочном состояние. И иногда возникает необходимость упорядочивания данные прежде чем их можно будет эффективно использовать. За все эти годы учеными было создано множество алгоритмов сортировки для организации данных.
В этой статье мы рассмотрим наиболее популярные алгоритмы сортировки, разберем, как они работают, и напишем их на Python. Мы также сравним, как быстро они сортируют элементы в списке.
Для простоты реализации алгоритмов сортировать числа будем в порядке их возрастания.
Пузырьковая сортировка (Bubble Sort)
Этот самый простой алгоритм сортировки который выполняет итерации по списку, сравнивая элементы попарно и меняя их местами, пока более крупные элементы не перестанут «всплывать» до конца списка, а более мелкие элементы не будут оставаться «снизу».
Объяснение
Начнем со сравнения первых двух элементов списка. Если первый элемент больше второго, мы меняем их местами. Если они уже в нужном порядке, мы оставляем их как есть. Затем мы переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.
Достигнув конца списка, повторяем этот процесс для каждого элемента снова. Хотя это крайне неэффективно. Что если в массиве нужно сделать только одну замену? Почему мы все еще повторяем, даже если список уже отсортирован? Получается нам нужно пройти список n^2 раза.
Очевидно, что для оптимизации алгоритма нам нужно остановить его, когда он закончит сортировку.
Откуда нам знать, что мы закончили сортировку? Если бы элементы были отсортированы, то нам не пришлось бы их менять местами. Таким образом, всякий раз, когда мы меняем элементы, мы устанавливаем флаг в True, чтобы повторить процесс сортировки. Если перестановок не произошло, флаг останется False, и алгоритм остановится.
Реализация
Мы можем реализовать пузырьковую сортировку в Python следующим образом:
def bubble_sort(nums): # We set swapped to True so the loop looks runs at least once swapped = True while swapped: swapped = False for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: # Swap the elements nums[i], nums[i + 1] = nums[i + 1], nums[i] # Set the flag to True so we'll loop again swapped = True # Verify it works random_list_of_nums = [5, 2, 1, 8, 4] bubble_sort(random_list_of_nums) print(random_list_of_nums)
Алгоритм работает в цикле while, прерываясь только тогда, когда никакие элементы не меняются местами. Вначале мы установили для swapped значение True, чтобы алгоритм прошел по списку хотя бы один раз.
Сложность
Сложность пузырьковой сортировки в худшем случае (когда список отсортирован в обратном порядке) равна O(n^2).
Сортировка выбором (Selection Sort)
Этот алгоритм сегментирует список на две части: отсортированные и несортированные. Он постоянно удаляет наименьший элемент из несортированного сегмента списка и добавляет его в отсортированный сегмент.
Объяснение
На практике нам не нужно создавать новый список для отсортированных элементов, мы будет обрабатывать крайнюю левую часть списка как отсортированный сегмент. Затем мы ищем во всем списке наименьший элемент и меняем его на первый элемент.
Теперь мы знаем, что первый элемент списка отсортирован, мы получаем наименьший элемент из оставшихся элементов и заменяем его вторым элементом. Это повторяется до тех пор, пока последний элемент списка не станет оставшимся элементом для изучения.
Реализация
def selection_sort(nums): # значение i соответствует тому, сколько значений было отсортировано for i in range(len(nums)): # Мы предполагаем, что первый элемент несортированного сегмента является наименьшим lowest_value_index = i # Этот цикл перебирает несортированные элементы for j in range(i + 1, len(nums)): if nums[j] < nums[lowest_value_index]: lowest_value_index = j # Поменять местами значения самого низкого несортированного элемента с первым несортированным nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i] # Проверяем, что это работает random_list_of_nums = [12, 8, 3, 20, 11] selection_sort(random_list_of_nums) print(random_list_of_nums)
Мы видим, что по мере того как i увеличивается, нам нужно проверять все меньше элементов.
Сложность
Сложность сортировки выбором в среднем составляет O(n^2).
Сортировка вставками (Insertion Sort)
Как и Сортировка выбором, этот алгоритм сегментирует список на отсортированные и несортированные части. Он перебирает несортированный сегмент и вставляет просматриваемый элемент в правильную позицию отсортированного списка.
Объяснение
Предполагается, что первый элемент списка отсортирован. Затем мы переходим к следующему элементу, назовем его х. Если x больше первого элемента, мы оставляем его как есть. Если x меньше, мы копируем значение первого элемента во вторую позицию и затем устанавливаем первый элемент в x.
Когда мы переходим к другим элементам несортированного сегмента, мы непрерывно перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x, или не достигнем конца отсортированного сегмента, а затем поместим x в его правильное положение.
Реализация
def insertion_sort(nums): # Начнем со второго элемента, так как мы предполагаем, что первый элемент отсортирован for i in range(1, len(nums)): item_to_insert = nums[i] # И сохранить ссылку на индекс предыдущего элемента j = i - 1 # Переместить все элементы отсортированного сегмента вперед, если они больше, чем элемент для вставки while j >= 0 and nums[j] > item_to_insert: nums[j + 1] = nums[j] j -= 1 # Вставляем элемент nums[j + 1] = item_to_insert # Проверяем, что это работает random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums)
Сложность
Сложность сортировки вставками в среднем равна O(n^2).
Пирамидальная сортировка (Heap Sort) (англ. Heapsort, «Сортировка кучей»)
Этот популярный алгоритм сортировки, как сортировки вставками и выбором, сегментирует список на отсортированные и несортированные части. Он преобразует несортированный сегмент списка в структуру данных типа куча (heap), чтобы мы могли эффективно определить самый большой элемент.
Объяснение
Мы начинаем с преобразования списка в Max Heap – бинарное дерево, где самым большим элементом является корневой узел. Затем мы помещаем этот элемент в конец списка. Затем мы восстанавливаем нашу Max Heap, которая теперь имеет на одно меньшее значение, помещая новое наибольшее значение перед последним элементом списка.
Мы повторяем этот процесс построения кучи, пока все узлы не будут удалены.
Реализация
Мы создаем вспомогательную функцию heapify для реализации этого алгоритма:
def heapify(nums, heap_size, root_index): # Предположим, что индекс самого большого элемента является корневым индексом largest = root_index left_child = (2 * root_index) + 1 right_child = (2 * root_index) + 2 # Если левый потомок корня является допустимым индексом, а элемент больше # чем текущий самый большой элемент, то обновляем самый большой элемент if left_child < heap_size and nums[left_child] >nums[largest]: largest = left_child # Делайте то же самое для right_child if right_child < heap_size and nums[right_child] >nums[largest]: largest = right_child # Если самый большой элемент больше не является корневым элементом, меняем их местами if largest != root_index: nums[root_index], nums[largest] = nums[largest], nums[root_index] # Heapify the new root element to ensure it's the largest heapify(nums, heap_size, largest) def heap_sort(nums): n = len(nums) # Создаем Max Heap из списка # Второй аргумент означает, что мы останавливаемся на элементе перед -1, то есть на первом элементе списка. # Третий аргумент означает, что мы повторяем в обратном направлении, уменьшая количество i на 1 for i in range(n, -1, -1): heapify(nums, n, i) # Перемещаем корень max hea в конец for i in range(n - 1, 0, -1): nums[i], nums[0] = nums[0], nums[i] heapify(nums, i, 0) # Проверяем, что все работает random_list_of_nums = [35, 12, 43, 8, 51] heap_sort(random_list_of_nums) print(random_list_of_nums)
Сложность
В среднем сложность сортировки кучи составляет O(nlog (n)), что уже значительно быстрее, чем в предыдущих алгоритмах.
Сортировка слиянием (Merge Sort)
Этот алгоритм «разделяй и властвуй» разбивает список пополам и продолжает разбивать список на пары, пока в нем не будут только одиночные элементы.
Соседние элементы становятся отсортированными парами, затем отсортированные пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока мы не получим отсортированный список со всеми элементами несортированного списка.
Объяснение
Мы рекурсивно разделяем список пополам, пока не получим списки с одиночным размером. Затем мы объединяем каждую половину, которая была разделена, и при этом сортируя их.
Сортировка осуществляется путем сравнения наименьших элементов каждой половины. Первый элемент каждого списка сравнивается с первым. Если первая половина начинается с меньшего значения, то мы добавляем ее в отсортированный список. Затем мы сравниваем второе наименьшее значение первой половины с первым наименьшим значением второй половины.
Каждый раз, когда мы выбираем меньшее значение в начале половины, мы перемещаем индекс, элемент которого нужно сравнить на единицу.
Реализация
def merge(left_list, right_list): sorted_list = [] left_list_index = right_list_index = 0 # Мы будет часто используем длины списков, поэтому удобно сразу создавать переменные для этого left_list_length, right_list_length = len(left_list), len(right_list) for _ in range(left_list_length + right_list_length): if left_list_index < left_list_length and right_list_index < right_list_length: # Мы проверяем, какое значение с начала каждого списка меньше # Если элемент в начале левого списка меньше, добавляем его в отсортированный список if left_list[left_list_index]Обратите внимание, что функция merge_sort(), в отличие от предыдущих алгоритмов сортировки, возвращает новый отсортированный список, а не сортирует существующий список.
Поэтому для сортировки слиянием требуется пространство в памяти для создания нового списка того же размера, что и входной список.
Сложность
В среднем сложность сортировки слиянием составляет O(nlog (n)).
Быстрая сортировка (Quick Sort)
Это то же алгоритм «разделяй и властвуй» и его наиболее часто используют их описанных в этой статье. При правильной настройке он чрезвычайно эффективен и не требует дополнительного пространства памяти как сортировка слиянием. Мы разделяем список вокруг элемента точка опоры, сортируя значения вокруг этой точки.
Объяснение
Быстрая сортировка начинается с разбиения списка – выбора одного значения списка, которое будет в его отсортированном месте. Это значение называется опорным. Все элементы, меньшие, чем этот элемент, перемещаются влево. Все более крупные элементы перемещены вправо.
Зная, что опорный элемент находится на своем правильном месте, мы рекурсивно сортируем значения вокруг этого элемента, пока не будет отсортирован весь список.
Реализация
# Есть разные способы реализовать быструю сортировки # мы выбрали схема Tony Hoare def partition(nums, low, high): # Мы выбираем средний элемент, в качестве опорного. Некоторые реализации выбирают # первый элемент или последний элемент или вообще случайный элемент. pivot = nums[(low + high) // 2] i = low - 1 j = high + 1 while True: i += 1 while nums[i] < pivot: i += 1 j -= 1 while nums[j] >pivot: j -= 1 if i >= j: return j # Если элемент в i (слева от оси) больше, чем # элемент в J (справа от оси), то поменять их местами nums[i], nums[j] = nums[j], nums[i] def quick_sort(nums): # Создаем вспомогательную рекурсивную функцию def _quick_sort(items, low, high): if low < high: # Это индекс после опорного элемента, по которому наши списки разделены split_index = partition(items, low, high) _quick_sort(items, low, split_index) _quick_sort(items, split_index + 1, high) _quick_sort(nums, 0, len(nums) - 1) # Проверяем, что все работает random_list_of_nums = [22, 5, 1, 18, 99] quick_sort(random_list_of_nums) print(random_list_of_nums)Сложность
В среднем сложность быстрой сортировки составляет O(nlog (n)).
Примечание. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент будет наименьшим или наибольшим элементом списка. Быстрая сортировка обычно работает быстрее с более сбалансированными значениями. В отличие от сортировки кучи и сортировки слиянием, обе из которых имеют худшие времена O(nlog (n)), быстрая сортировка имеет худшее время O(n^2).
Встроенные функции сортировки Python
Хотя полезно знать и понимать эти алгоритмы сортировки, в большинстве проектов Python вы, вероятно, будете использовать встроенную функцию сортировки.
Создадим новый список, чтобы отсортировать его содержимое с помощью метода sort():
apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2] apples_eaten_a_day.sort() print(apples_eaten_a_day) # [1, 1, 1, 2, 2, 2, 3]Или мы можем использовать функцию sorted() для создания нового отсортированного списка:
apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2] sorted_apples = sorted(apples_eaten_a_day_2) print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3]Они оба сортируются в порядке возрастания, но вы можете легко отсортировать в порядке убывания, установив для флага реверса в значение True:
# Reverse sort the list in-place apples_eaten_a_day.sort(reverse=True) print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1] # Reverse sort to get a new list sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True) print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1]В отличие от созданных нами функций алгоритма сортировки, обе эти функции могут сортировать списки кортежей и классов. Функция sorted() может сортировать любой итеративный объект, который включает в себя – списки, строки, кортежи, словари, наборы (set) и пользовательские итераторы.
Встроенная функция сортировки реализуют алгоритм сортировки Тима. Этот алгоритм, основан на сортировке слиянием и сортировке вставкой.
Сравнение скорости
Чтобы понять, как быстро работают рассмотренные алгоритмы, мы сгенерируем список из 5000 чисел от 0 до 1000. Затем мы определим время, необходимое для завершения каждого алгоритма. Повторим это 10 раз, чтобы мы могли более надежно установить производительность сортировки.
Вот какие результаты мы получили, время в секундах:
| Run | Bubble Пузырьковая |
Selection Выбором |
Insertion Вставкой |
Heap Пирамидальная |
Merge Слиянием |
Quick Быстрая |
|---|---|---|---|---|---|---|
| 1 | 5.531886100769043 | 1.2315289974212646 | 1.6035542488098145 | 0.04006671905517578 | 0.0261991024017334 | 0.016391992568969727 |
| 2 | 4.921762228012085 | 1.2472858428955078 | 1.5910329818725586 | 0.03999590873718262 | 0.025842905044555664 | 0.01661396026611328 |
| 3 | 4.916421890258789 | 1.2244019508361816 | 1.5936298370361328 | 0.044072866439819336 | 0.028622865676879883 | 0.01646280288696289 |
| 4 | 5.154704332351685 | 1.2505383491516113 | 1.6346361637115479 | 0.04128289222717285 | 0.028828144073486328 | 0.01860785484313965 |
| 5 | 4.955228805541992 | 1.2898740768432617 | 1.61759614944458 | 0.04515719413757324 | 0.033148765563964844 | 0.01885080337524414 |
| 6 | 5.049072980880737 | 1.2546651363372803 | 1.625154972076416 | 0.042572975158691406 | 0.02595210075378418 | 0.01628708839416504 |
| 7 | 5.05591893196106 | 1.2491188049316406 | 1.6198101043701172 | 0.040289878845214844 | 0.027335166931152344 | 0.017602920532226562 |
| 8 | 5.087991952896118 | 1.2580881118774414 | 1.6260371208190918 | 0.04264688491821289 | 0.02633810043334961 | 0.017055988311767578 |
| 9 | 5.032891750335693 | 1.2491509914398193 | 1.6144649982452393 | 0.04302191734313965 | 0.032937049865722656 | 0.0176239013671875 |
| 10 | 5.142928838729858 | 1.2202110290527344 | 1.5727391242980957 | 0.03966116905212402 | 0.0257260799407959 | 0.016061067581176758 |
| Avg | 5.084880781173706 | 1.2474863290786744 | 1.6098655700683593 | 0.04187684059143067 | 0.02809302806854248 | 0.017155838012695313 |
Вы можете получить другие значения, если попробуете повторить тест самостоятельно, но общее соотношение должно быть одинаковым или похожим. Пузырьковая сортировка (Bubble Sort) – самая медленная и наихудшая из всех алгоритмов. Хотя она очень полезно в качестве введения в изучения алгоритмов сортировки, оно не подходит для практического использования.
Мы также заметили, что быстрая сортировка выполняется очень быстро, почти в два раза быстрее, чем сортировка слиянием, и для ее работы не требуется много памяти. Напомним, что наш опорный элемент был основан на среднем элементе списка, разные опорные элементы могут дать разные результаты.
Поскольку сортировка вставкой выполняет намного меньше сравнений, чем сортировка выбором, то обычно она выполняются быстрее, но в нашем тесте сортировка выбором выполнилась немного быстрее.
Сортировка вставкой делает гораздо больше замен, чем сортировка выбором. Скорее всего обмен значениями занял значительно больше времени, чем сравнение значений, поэтому мы получили этот «противоположный» результат.
При выборе алгоритма сортировки следует помнить о самих данных и среде запуска алгоритмов, так как это тоже влияет на производительность.
Заключение
Алгоритмы сортировки дают нам много способов упорядочить наши данные. Мы рассмотрели 6 различных алгоритмов – Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort – и их реализации в Python.
Количество сравнений и перестановок, которые выполняет алгоритм вместе со средой, в которой выполняется код, являются ключевыми определяющими факторами производительности. В реальных приложениях Python рекомендуется придерживаться встроенных функций сортировки Python из-за их гибкости и скорости.
Сортировка словаря в Python по значению
В области программирования на языке Python часто возникает ситуация, когда необходимо отсортировать словарь по значению. Подобная задача может возникнуть, например, при обработке больших объемов данных, когда необходимо сортировать словарь для удобства визуального анализа или для дальнейшей обработки данных.
Рассмотрим пример. Есть словарь, где ключами являются имена, а значениями — возраст:
people =
Предположим, что требуется отсортировать этот словарь по возрасту в порядке возрастания.
В Python для этого можно использовать встроенную функцию sorted() . Однако, стандартное применение этой функции к словарю приведет к сортировке по ключам, а не по значениям. Чтобы сортировать по значениям, необходимо указать аргумент key в функции sorted() .
В качестве этого аргумента можно передать функцию, которая будет применена к каждому элементу перед сравнением. Для доступа к значениям словаря в Python используется метод get() .
Итак, для сортировки словаря по значению в порядке возрастания можно использовать следующий код:
sorted_people = sorted(people.items(), key=lambda item: item[1])
В этом коде people.items() возвращает пары (ключ, значение), key=lambda item: item[1] указывает, что сортировка происходит по значению (второму элементу пары), а не по ключу.
Результатом выполнения этого кода будет список кортежей:
[('Маша', 20), ('Вася', 25), ('Петя', 30)]
Если же требуется отсортировать словарь по значению в порядке убывания, нужно добавить аргумент reverse=True в функцию sorted() :
sorted_people = sorted(people.items(), key=lambda item: item[1], reverse=True)
[('Петя', 30), ('Вася', 25), ('Маша', 20)]
Таким образом, можно легко сортировать словари в Python по значению, используя встроенные функции и методы.