сортировка выбором питон код
Топ-5 алгоритмов сортировки на Python
Сортировка — это навык, которым должен обладать каждый программист. Не только для прохождения собеседований, но и для понимания дисциплины в целом. Разные алгоритмы сортировки — отличная демонстрация того, как внутренняя логика может влиять на сложность, скорость и эффективность программы.
Разберем 5 самых распространенных алгоритмов и реализуем их в Python.
Bubble Sort (пузырьковая сортировка)
Этот вид сортировки изучают в начале знакомства с дисциплиной Computer Science, поскольку он максимально просто демонстрирует саму концепцию сортировки.
При этом подходе осуществляется перебор по списку и сравнение соседних элементов. Они меняются местами в том случае, если порядок неправильный. Так продолжается до тех пор, пока все элементы не расположатся в нужном порядке. Из-за большого количества повторений у пузырьковой сортировки его сложность в худшем случае — O(n^2).
Selection Sort (сортировка выбором)
Сортировка выбором — также простой алгоритм, но более эффективный по сравнению с пузырьковой сортировкой. В большинстве случаев сортировка выбором будет более удачным выбором из двух.
В этом алгоритме список (или массив) делится на две части: список с отсортированными элементами и список с элементами, которые только нужно сортировать. Сначала ищется самый маленький элемент во втором. Он добавляется в конце первого. Таким образом алгоритм постепенно формирует список от меньшего к большему. Так происходит до тех пор, пока не будет готовый отсортированный массив.
Insertion Sort (сортировка вставками)
Сортировка вставками быстрее и проще двух предыдущих. Именно так большинство людей тасует карты любой игре. На каждой итерации программа берет один из элементов и подыскивает для него место в уже отсортированном списке. Так происходит до тех пор, пока не останется ни одного неиспользованного элемента.
Merge Sort (сортировка слиянием)
Сортировка слиянием — элегантный пример использования подхода «Разделяй и властвуй». Он состоит из двух этапов:
Quick Sort (быстрая сортировка)
Как и сортировка слиянием, быстрая сортировка использует подход «Разделяй и властвуй». Алгоритм чуть сложнее, но в стандартных реализациях он работает быстрее сортировки слиянием, а его сложность в худшем случае редко достигает O(n^2). Он состоит из трех этапов:
Алгоритмы сортировки на Python
Иногда данные, которые мы храним или получаем в приложении, не упорядочены. Это затрудняет их обработку и использование. Но если имеющиеся данные отсортировать по какому-то принципу и поместить в упорядоченный список, работа с ними станет гораздо эффективнее. Здесь нам на помощь приходят алгоритмы сортировки. Они широко применяются, например, при написании поисковиков и в работе с базами данных.
Алгоритмов сортировки довольно много. К самым распространенным можно отнести сортировку выбором, пузырьком, перемешиванием, вставками, слиянием.
Все эти алгоритмы отличаются подходами к упорядочиванию элементов в списках и, как следствие этого, скоростью работы в разных ситуациях.
Естественно, все мы хотим, чтобы наши программы работали максимально быстро. Для этого нужно выбирать наиболее подходящие для заданных условий алгоритмы. Как узнать, какой из них быстрее и эффективнее?
Ну, во-первых, следует изучить принцип работы каждого. А во-вторых, быстродействие (временная сложность) самых распространенных алгоритмов давно изучено, измерено и выражено в формулах (для наилучшего, наихудшего и среднего случаев). Когда вы поближе познакомитесь с алгоритмами сортировки и разберетесь в их временной сложности, вы сможете более уверенно выбирать подходящий вариант для конкретной ситуации.
На нашем сайте вы найдете целую серию статей, посвященных алгоритмам и, в частности, алгоритмам сортировки. В этих материалах мы рассматриваем самые популярные алгоритмы, рассказываем, как они работают, а также приводим примеры их реализации в коде на Python. Последнее особенно важно, ведь теоретических материалов по алгоритмам довольно много, но каждому программисту хочется в первую очередь увидеть, как все это выглядит в коде.
Итак, предлагаем вам познакомиться со следующими алгоритмами сортировки:
Сортировки выбором
В чём идея сортировок выбором?
Однако, сейчас в тренде нелинейность, поэтому, не написав ещё все публикации про сортировки вставками, сегодня начну параллельную ветку про сортировки выбором. То же самое потом сделаю для других алгоритмических классов: сортировок слиянием, сортировок распределением и т.п. Это в целом позволит писать публикации то по одной теме, то по другой. С таким тематическим чередованием будет веселее.
Сортировка выбором :: Selection sort
Просто и незатейливо — проходим по массиву в поисках максимального элемента. Найденный максимум меняем местами с последним элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает последний элемент, куда мы переставили найденный максимум). К этой неотсортированной части применяем те же действия — находим максимум и ставим его на последнее место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.
Сортировка простым выбором представляет из себя грубый двойной перебор. Можно ли её улучшить? Разберём несколько модификаций.
Двухсторонняя сортировка выбором :: Double selection sort
Похожая идея используется в шейкерной сортировке, которая является вариантом пузырьковой сортировки. Проходя по неотсортированной части массива, мы кроме максимума также попутно находим и минимум. Минимум ставим на первое место, максимум на последнее. Таким образом, неотсортированная часть при каждой итерации уменьшается сразу на два элемента.
На первый взгляд кажется, что это ускоряет алгоритм в 2 раза — после каждого прохода неотсортированный подмассив уменьшается не с одной, а сразу с двух сторон. Но при этом в 2 раза увеличилось количество сравнений, а число свопов осталось неизменным. Двойной выбор лишь незначительно увеличивает скорость алгоритма, а на некоторых языках даже почему-то работает медленнее.
Отличие сортировок выбором от сортировок вставками
Может показаться, что сортировки выбором и сортировки вставками — это суть одно и то же, общий класс алгоритмов. Ну, или сортировки вставками — разновидность сортировок выбором. Или сортировки выбором — частный случай сортировок вставками. И там и там мы по очереди из неотсортированной части массива извлекаем элементы и перенаправляем их в отсортированную область.
Главное отличие: в сортировке вставками мы извлекаем из неотсортированной части массива любой элемент и вставляем его на своё место в отсортированной части. В сортировке выбором мы целенаправленно ищем максимальный элемент (или минимальный), которым дополняем отсортированную часть массива. Во вставках мы ищем куда вставить очередной элемент, а в выборе — мы заранее уже знаем в какое место поставим, но при этом требуется найти элемент, этому месту соответствующий.
Это делает оба класса алгоритмов совершенно отличными друг от друга по своей сути и применяемым методам.
Бинго-сортировка :: Bingo sort
Интересной особенностью сортировки выбором является независимость скорости от характера сортируемых данных.
Например, если массив почти отсортирован, то, как известно, сортировка вставками его обработает гораздо быстрее (даже быстрее чем быстрая сортировка). А реверсно упорядоченный массив для сортировки вставками является вырожденным случаем, она будет его сортировать максимально долго.
А для сортировки выбором частичная или реверсная упорядоченность массива роли не играет — она обработает его примерно с той же скоростью что и обычный рандом. Также для классической сортировки выбором неважно, состоит ли массив из уникальных или повторяющихся элементов — на скорость это практически не влияет.
Но в принципе, можно исхитриться и модифицировать алгоритм так, чтобы при некоторых наборах данных работало быстрее. Например, бинго-сортировка учитывает, если массив состоит из повторяющихся элементов.
Здесь фокус в том, что в неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации. Это позволяет при повторяющихся максимумах не искать их заново каждый раз, а ставить на своё место сразу как только этот максимум в очередной раз встретили в массиве.
Алгоритмическая сложность осталась та же. Но если массив состоит из повторяющихся чисел, то бинго-сортировка справится в десятки раз быстрее, чем обычная сортировка выбором.
Цикличная сортировка :: Cycle sort
Цикличная сортировка интересна (и ценна с практической точки зрения) тем, что изменения среди элементов массива происходят тогда и только тогда, когда элемент ставится на своё конечное место. Это может пригодиться, если перезапись в массиве — слишком дорогое удовольствие и для бережного отношения к физической памяти требуется свести к минимуму количество изменений элементов массива.
Работает это так. Перебираем массив, назовём X очередную ячейку в этом внешнем цикле. И смотрим на какое место в массиве нужно вставить очередной элемент из этой ячейки. На том месте, куда нужно вставить находится какой-то другой элемент, его отправляем в буфер обмена. Для этого элемента в буфере тоже ищем его место в массиве (и вставляем на это место, а в буфер отправляем элемент, оказавшийся в этом месте). И для нового числа в буфере производим те же действия. До каких пор должен продолжаться этот процесс? Пока очередной элемент в буфере обмена не окажется тем элементом, который нужно вставить именно в ячейку X (текущее место в массиве в главном цикле алгоритма). Рано или поздно этот момент произойдёт и тогда во внешнем цикле можно перейти к следующей ячейке и повторить для неё ту же процедуру.
В других сортировках выбором мы ищем максимум/минимум, чтобы поставить их на последнее/первое место. В cycle sort так получается, что минимум на первое место в подмассиве как бы находится сам, в процессе того, как несколько других элементов ставятся на свои законные места где-то в середине массива.
И здесь алгоритмическая сложность так же остаётся в пределах O(n 2 ). На практике цикличная сортировка работает даже в несколько раз медленнее, чем обычная сортировка выбором, так как приходится больше бегать по массиву и чаще сравнивать. Это цена за минимально возможное количество перезаписей.
Блинная сортировка
Алгоритм, который освоили все уровни жизни — от бактерий до Билла Гейтса.
В самом простом варианте мы в неотстортированной части массива ищем максимальный элемент. Когда максимум найден — делаем два резких разворота. Сначала переворачиваем цепочку элементов так, чтобы максимум оказался на противоположном конце. Затем переворачиваем весь неотсортированный подмассив, в результате чего максимум попадает на своё место.
Подобные кордибалеты, вообще говоря, приводят к алгоритмической сложности в O(n 3 ). Это дрессированные инфузории кувыркаются одним махом (поэтому в их исполнении сложность O(n 2 )), а при программировании разворот части массива — это дополнительный цикл.
Блинная сортировка очень интересна с математической точки зрения (лучшие умы размышляли над оценкой минимального количества переворотов, достаточных для сортировки), есть более сложные постановки задачи (с так называемой подгоревшей одной стороной). Тема блинов крайне интересная, возможно, напишу более обстоятельную монографию по этим вопросам.
Сортировка выбором эффективна настолько, насколько эффективно организован поиск минимального/максимального элемента в неотсортированной части массива. Во всех разобранных сегодня алгоритмах поиск осуществляется в виде двойного перебора. А у двойного перебора, как ни крути, алгоритмическая сложность будет всегда не лучше чем O(n 2 ). Значит ли это, что все сортировки выбором обречены на средне-квадратичную сложность? Вовсе нет, если процесс поиска организовать принципиально по-другому. Например рассмотреть набор данных как кучу и производить поиск именно в куче. Однако тема кучи — это даже не на статью, а на целую сагу, о кучах поговорим обязательно, но в другой раз.
Ссылки
Selection / Выбор, Cycle, Pancake / Блины
Шпаргалка по сортировке для Data Science
Сортировка данных является основной задачей для ученых и инженеров по обработке данных. Пользователи Python могут выбирать наиболее удобную из ряда библиотек со встроенными, оптимизированными опциями сортировки. Некоторые даже работают параллельно с GPU. На удивление, некоторые методы сортировки не используют указанные типы алгоритмов, а другие работают совсем не так, как ожидалось.
Выбор библиотеки и типа алгоритма сортировки не всегда прост, а нововведения меняются в быстром темпе. На данный момент документация Pandas не соответствует коду (хотя лично мое PR-обновление сортировочных опций было самым последним).
В этой статье я разъясню вам, что к чему, дам пару советов, которые помогут с разобраться с методами, и поделюсь результатами теста скорости.
Контекст
Базовых алгоритмов сортировки существует множество. Одни из них имеют высокую производительность и занимают меньше места, другие хорошо работают с большим числом данных. Для некоторых алгоритмов важно взаимное расположение элементов данных. На диаграмме в начале статьи можно увидеть ситуацию по времени и объему для самых распространенных алгоритмов.
На самом деле, не нужно быть экспертом в базовых внедрениях, чтобы решить большинство проблем сортировки. На деле, корнем зла порой считают преждевременную оптимизацию. Однако, при необходимости многократной сортировки большого числа данных может оказаться весьма полезным знать заранее, какую библиотеку и какие ключевые слова лучше использовать. Представляю вам мою шпаргалку.
За многие годы алгоритмы сортировки изменились в большинстве библиотек. Для анализа в этой статье я взял следующие версии ПО.
Python (vanilla)
Python содержит два встроенных метода сортировки.
Все реализации для Vanilla Python, которые мы рассмотрим в этой статье, имеют восходящий порядок сортировки по умолчанию — от наименьшего до наибольшего. Однако, большинство иных методов сортировки используют нисходящий метод. Не слишком-то удобно для вас и вашей головы, но этот параметр разнится в каждой библиотеке.
key может быть заявлен ключевым словом для вашего уникального критерия. Например, sort(key=len) отсортирует элементы списка по их длине.
Единственный алгоритм сортировки, используемый в Vanilla Python — Timsort. Посредством данного алгоритма сортировка данных производится по их основным критериям. Например, если требуется сортировать короткий список, используется сортировка вставками. Дополнительную информацию о Timsort см. в большой статье Брэндона Скерритта.
Теперь предлагаю рассмотреть использование Numpy.
Numpy
Numpy — это фундаментальная библиотека Python для научных вычислений. Как и у Vanilla Python, вариантов реализации у нее два: либо копирование, либо изменение массива исходных данных:
В случае, если удовлетворительного результата нет, происходит переключение на алгоритм heapsort. В худшем случае сортировка происходит по быстрому циклу O(n* log (n)).
stable автоматически выбирает наиболее приемлемый вариант сортировки. Данный параметр, наряду с сортировкой слиянием, на данный момент сопоставляется с сортировкой timsort или radix, в зависимости от типа данных. Прямая совместимость API в настоящее время ограничивает возможность выбора реализации, и она жестко привязана к различным типам данных.
Timsort применяется на предварительно подготовленных или близких к финальной сортировке данных. По случайным данным timsort практически идентичен mergesort. На данный момент он используется для конкретной сортировки, в то время как быстрая сортировка по-прежнему реализуется по умолчанию, и если конкретного выбора нет… «mergesort» и «stable» выполняются для целочисленных типов данных автоматически.
— Из документов Numpy — (после парочки моих правок)
Один из важнейших выводов: Numpy позволяет управлять параметрами сортировки более свободно, чем Vanilla Python. Второй вывод, не менее важный: ключевое слово kind совершенно не обязательно соответствует используемому типу сортировки. И наконец, финальный итог, если можно так сказать, заключается в том, что mergesort и stable являются определенными сортировками, а quicksort и heapsort — нет.
Все функции Numpy также доступны в куда более удобном для использования Pandas.
Pandas
Поскольку “под капотом” у Pandas — Numpy, у вас под рукой есть те же оптимизированные параметры сортировки. Тем не менее, использование Pandas чуть более трудозатратно.
Для Pandas есть несколько ключевых моментов, которые стоит запомнить:
Dask, который Pandas предлагают для работы с большими данными, пока что не имеет реализации параллельной сортировки, но этот вопрос находится в обсуждении.
Сортировка в Pandas — это хороший выбор для предварительной сортировки небольших объемов данных. Если же вы имеете большой объем данных и хотите параллельно работать с GPU, стоит обратить внимание на TensorFlow или PyTorch.
TensorFlow
TensorFlow — самая популярная среда для deep learning. Больше о глубоком изучении можно узнать в моей статье по ссылке здесь. Приведенная ниже информация актуальна для GPU TensorFlow 2.0.
tf.sort(my_tensor) возвращает отсортированную копию тензора. Опциональные аргументы:
Для проверки кода на CPU и GPU используйте следующую строку:
Чтобы указать, что вы хотите использовать GPU, нужно воспользоваться таким блоком:
tf.sort() это интуитивно понятный метод при работе в TensorFlow. Просто запомните, что direction=descending нужен для изменения порядки сортировки.
PyTorch
torch.sort(my_tensor) возвращает отсортированную копию тензора. Необязательные аргументы:
Исследования показали, что PyTorch использует сегментированную параллельную сортировку через Thrust, если сортируется набор данных размером более 1 миллиона строк на 100 000 столбцов.
К сожалению, у меня не хватило памяти, когда я пытался создать произвольные данные размером 1.1 миллиона на 100 тысяч через Numpy в Google Colab. После этого я попробовал GCP с 416 МБ ОЗУ, и мне вновь не хватило памяти.
Сегментированная сортировка и сортировка по местоположению — это высокопроизводительные варианты сортировки слиянием, которые работают с неоднородными случайными данными. Сегментированная сортировка позволяет сортировать множество массивов переменной длины параллельно. — https://moderngpu.github.io/segsort.html
Thrust — это библиотека параллельных алгоритмов, которая обеспечивает совместимость производительности GPU и многояденых CPU. Она предоставляет сортировочную основу, которая автоматически выбирает наиболее эффективный метод реализации. Библиотека CUB, используемая TensorFlow, облегчает нагрузку. PyTorch и TensorFlow используют аналогичные алгоритмы для сортировки GPU — независимо от того, какой применяется подход.
Хотя сортировка с использованием GPU может выступать хорошим вариантом для очень больших наборов данных, также имеет смысл сортировать данные непосредственно в SQL.
Сортировка в SQL обычно выполняется очень быстро, особенно если сортировка происходит непосредственно в памяти.
Другие варианты SQL используют разные алгоритмы сортировки. Например, Google BigQuery использует внутреннюю сортировку с некоторыми приемами, вроде тех, что представлены в ответе на Stack Overflow.
Чтобы отсортировать данные по убыванию, используйте ключевое слово DESC. Таким образом, запрос на возврат данных в алфавитном порядке от последнего к первому будет выглядеть так:
Сравнение
Для каждой из вышеперечисленных библиотек Python я провел анализ, сортируя 1 000 000 точек данных в одном столбце, массиве или списке. Я использовал ноутбук Google Colab Jupyter с GPU K80 и Intel Xeon CPU с тактовой частотой 2,30 ГГц.
Наблюдения
Подведем итоги
Как правило, вам не нужны собственные разработки вариантов сортировки. Готовые варианты вполне удовлетворительны, и зачастую используют не один метод сортировки. Вместо этого они сначала оценивают данные, а затем используют проверенный алгоритм сортировки. Некоторые версии даже модифицируют алгоритмы, если сортировка подтормаживает.
В этой статье вы поняли, как сортировать каждый фрагмент данных в Python и SQL. Я надеюсь, вам это поможет в будущем. Если у вас есть такая возможность, пожалуйста, поделитесь статьей в ваших любимых социальных сетях, чтобы помочь другим людям найти ее.
Вам все лишь нужно запомнить, какой вариант выбрать и его вызвать. Используйте мою шпаргалку, чтобы сэкономить время. Мои общие рекомендации звучат так:
Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя платные онлайн-курсы SkillFactory:
Алгоритмы сортировки на Python
Сортировка — это базовый элемент построения многих алгоритмов и связана она с захватывающими идеями. Понимание того, как за кулисами в Python работают алгоритмы сортировки, является основополагающим шагом при реализации правильных и эффективных алгоритмов, решающих реальные проблемы.
В этом уроке вы узнаете:
В результате вы поймете как с теоретической, так и с практической точек зрения, что такое алгоритмы сортировки. Сможете использовать различные методы при разработке алгоритмов, которые можно использовать и в других областях своей работы. Давайте начинать!
Содержание
Почему алгоритмов сортировки так важны?
Алгоритмы сортировки является наиболее тщательно изученными алгоритмами Computer Science. Существуют десятки различных реализаций сортировки и приложений. Сортировка необходима при решении широкого круга задач:
От создания коммерческих приложений до академических исследований, повсюду, есть масса способов осуществить сортировку, позволяющую сэкономить время и силы.
Встроенный алгоритм сортировки
Python, как и многие другие языки программирования высокого уровня, имеют функции сортировки прямо из коробки, например, sorted() в Python:
Для сортировки любого списка можно использовать функцию sorted() при условии, что значения внутри списка можно сравнивать.
Примечание.
Для более глубокого погружения в работу встроенной функции сортировки Python, ознакомьтесь с разделом Как использовать sorted() и sort() в Python и Сортировка данных с помощью Python.
Почему так важно знать вычислительную сложность?
Вычислительная сложность એ — фундаментальное понятие вычислительной математики. В этом уроке рассматриваются два разных способа измерения сложности алгоритмов сортировки:
Вычислительная сложность вашего кода
В этом примере run_sorting_algorithm() получает имя алгоритма и входной массив, который необходимо отсортировать. Вот построчное объяснение того, как это работает:
Примечание:
Распространенным заблуждением является то, что вы должны найти среднее время каждого прогона алгоритма, а не выбирать единственное самое короткое время. Измерения времени шумят, потому что в системе одновременно запускаются и другие процессы. Самое короткое время всегда наименее зашумлённое, что делает его наилучшей оценкой истинного времени выполнения алгоритма.
Вот пример того, как использовать, run_sorting_algorithm() для оценки времени, необходимого для сортировки массива из десяти тысяч целочисленных значений, используя sorted() :
Помните, что время в секундах каждого эксперимента частично зависит от используемого вами оборудования, поэтому вы, скорее всего, увидите несколько иные результаты при запуске кода.
Примечание:
Вычислительная сложность એ в нотации «О»‑большое
Конкретного времени, которое требуется алгоритму недостаточно для получения полной картины его вычислительной сложности. Чтобы решить эту проблему, вы можете использовать обозначение «О»‑большое. «О»‑большое часто используется для сравнения различных реализаций и определения, какая из них наиболее эффективна, пропуская ненужные детали и концентрируясь на том, что является наиболее важным во время выполнения алгоритма. Время в секундах, необходимое для запуска различных алгоритмов, может зависеть от нескольких несвязанных факторов, включая скорость процессора или доступную память. «О»‑большое, с другой стороны, предоставляет платформу для выражения вычислительной сложности выполнения в не зависящем от аппаратного обеспечения виде. «О»‑большое показывает, как быстро увеличивается время выполнения вашего алгоритма в зависимости от размера входных данных, особенно когда входные данные становятся очень большими. Предполагая, что n — это размер входных данных алгоритма, нотация «О»‑большое представляет взаимосвязь между n и числом шагов, которые выполняет алгоритм до своего завершения. «О»‑большое использует заглавную букву «О», за которой в скобках следует обозначение зависимости. Например, O(n) представляет алгоритмы, которые выполняют последовательность шагов, количество которых пропорционально размеру входных данных. Хотя в этом уроке мы не собираемся углубляться в детали нотации «О»‑большое, но вот вам пять примеров вычислительной сложности различных алгоритмов:
Алгоритм сортировки методом «пузырька»
Метод «пузырька» или обменная сортировка — один из самых простых алгоритмов сортировки. Его название происходит от того, как работает алгоритм: с каждым новым проходом самый большой элемент «всплывает» к своему месту в упорядоченном списке. Пузырьковая сортировка состоит из нескольких проходов по списку, поэлементному сравнению с соседним элементом и, при необходимости, сменой порядка следования этих элементов.
Сортировка в Python методом «пузырька»
Вот реализация алгоритма сортировки «пузырьком» или обменная сортировка в Python:
Поскольку эта реализация упорядочивает массив по возрастанию, то на каждом шаге самый большой элемент «откладывается» в конце массива. Это означает, что каждая последующая итерация занимает меньше шагов, чем предыдущая. Циклы в строке 10 определяют способ просмотра списка. Обратите внимание, как j изначально идет от первого элемента в списке к элементу непосредственно перед последним. Во время второй итерации j цикл выполняется до второго элемента от последнего, затем до третьего элемента от последнего и т.д. В конце каждой итерации конечная часть списка будет отсортирована. По мере прохождения цикла строка 15 сравнивает каждый элемент с соседним значением, а строка 18 меняет их местами, если они находятся в неправильном порядке. Это гарантирует получение отсортированного списка при завершении алгоритма.
Примечание:
Флаг already_sorted в строках 13, и приведенного выше кода оптимизирует алгоритм и не требуется в полнофункциональной реализации пузырьковой сортировки. Тем не менее, он позволяет функции сохранять ненужные шаги, если список полностью сортируется до завершения циклов. В качестве упражнения вы можете отказаться от использования этого флага и сравнить время выполнения обеих реализаций.
Алгоритм сортировки методом «пузырька» (обменная сортировка)
Теперь пошагово посмотрим, что происходит с массивом в процессе работы алгоритма:
Оценка вычислительной сложности метода «пузырька»
Таким образом, а O(n) — сложность выполнения алгоритма методом «пузырька». Но надо иметь в виду, что лучший случай скорее исключением, а нам при сравнении различных алгоритмов надо сосредоточиться на более вероятных случаях.
Оценка времени выполнения алгоритма метода «пузырька»
Используем для вычисления времени выполнения алгоритма сортировки методом «пузырька» уже известный нам run_sorting_algorithm() для обработки массива с десятью тысячами элементов. В строке 8 заменим имя алгоритма, а все остальное оставим прежним:
Теперь можно запустить скрипт и получить время выполнения bubble_sort :
Потребовалось чуть больше 73 секунд для сортировки массива из десяти тысяч элементов. Это минимальное время из десяти run_sorting_algorithm() запущенных повторений. Многократное выполнение этого скрипта даст схожие результаты.
Примечание:
Преимущества и недостатки сортировки методом «пузырька» в Python
Алгоритм сортировки методом вставки
Подобно пузырьковой сортировке, алгоритм сортировки вставкой прост в реализации и понимании. Но в отличие от пузырьковой сортировки, он создает отсортированный список по одному элементу за раз, сравнивая каждый элемент с остальной частью списка и вставляя его в нужное место. Эта процедура «вставки» дает алгоритму его имя. Отличная аналогия для объяснения сортировки вставками — это способ сортировки колоды карт. Представьте, что вы держите в руках группу карт и хотите расположить их по порядку. Вы начнете со сравнения одной карты шаг за шагом с остальными картами, пока не найдете правильную позицию. В этот момент вы вставите карту в правильное место и начнете сначала с новой карты, повторяя, пока все карты в вашей руке не будут отсортированы.
Сортировка в Python методом вставки
Алгоритм сортировки вставок работает точно так же, как в примере с колодой карт. Вот реализация в Python:
В отличие от пузырьковой сортировки, эта реализация сортировки вставкой создает отсортированный список, перемещая меньшие элементы влево. Давайте разберем insertion_sort() построчно:
Вот рисунок, иллюстрирующий различные итерации алгоритма при сортировке массива [8, 2, 6, 4, 5] :
Алгоритм сортировки включением
Теперь вот краткое изложение шагов алгоритма при сортировке массива:
Оценка сложности «О»‑большое алгоритма вставки
Оценка времени выполнения сортировки вставкой
Чтобы доказать утверждение, что сортировка вставками более эффективна, чем сортировка по пузырькам, вы можете рассчитать время выполнения алгоритма сортировки по вставке и сравнить его с результатами сортировки по пузырькам. Для этого вам просто нужно заменить вызов run_sorting_algorithm() на имя вашей реализации сортировки вставкой:
Вы можете выполнить скрипт как раньше:
Обратите внимание, что реализация сортировки вставкой заняла примерно 17 меньше секунд, чем реализация пузырьковой сортировки, чтобы отсортировать тот же массив. Даже при том, что они оба O(n^2) алгоритмы, сортировка вставки более эффективна.
Преимущества и недостатки сортировки вставкой
Алгоритм сортировки слиянием
Сортировка слиянием — очень эффективный алгоритм сортировки. Он основан на подходе «разделяй и властвуй», мощном алгоритмическом методе, используемом для решения сложных задач. Чтобы правильно понять «разделяй и властвуй», вы должны сначала понять концепцию рекурсии. Рекурсия включает разбиение проблемы на более мелкие подзадачи, пока они не станут достаточно маленькими для управления. В программировании рекурсия обычно выражается функцией, вызывающей себя.
Примечание:
В этом урок мы не углубляемся в рассматрение рекурсии. Чтобы лучше понять, как работает рекурсия и увидеть ее в действии с использованием Python, ознакомьтесь с разделом «Рекурсивное мышление» в Python.
Алгоритмы «разделяй и властвуй» обычно имеют одинаковую структуру:
В случае сортировки слиянием подход «разделяй и властвуй» делит набор входных значений на две части одинакового размера, рекурсивно сортирует каждую половину и, наконец, объединяет эти две отсортированные части в один отсортированный список.
Сортировка в Python методом слиянием
Реализация алгоритма сортировки слиянием требует двух разных частей:
Вот код для объединения двух разных массивов:
merge() получает два разных отсортированных массива, которые необходимо объединить. Процесс для достижения этого прост:
При наличии вышеуказанной функции единственным отсутствующим элементом является функция, которая рекурсивно разделяет входной массив пополам и использует merge() для получения окончательного результата:
Вот краткое описание кода:
Обратите внимание, как эта функция вызывает себя рекурсивно, каждый раз уменьшая массив пополам. Каждая итерация имеет дело с постоянно уменьшающимся массивом до тех пор, пока не останется менее двух элементов, то есть сортировать нечего. В этот момент merge() вступает во владение, объединяя две половины и создавая отсортированный список. Посмотрите на представление шагов, которые сортировка слиянием предпримет для сортировки массива [8, 2, 6, 4, 5] :
Алгоритм сортировки слиянием
На рисунке используются желтые стрелки для представления деления массива пополам на каждом уровне рекурсии. Зеленые стрелки представляют слияние каждого подмассива обратно вместе. Шаги можно суммировать следующим образом:
Оценка сложности «О»‑большое алгоритма сортировки слиянием
Чтобы проанализировать сложность сортировки слиянием, вы можете взглянуть на два ее шага отдельно:
Оценка времени выполнения сортировки слиянием
Чтобы сравнить скорость сортировки слиянием с двумя предыдущими реализациями, вы можете использовать тот же механизм, что и раньше, и заменить имя алгоритма в строке 8 :
Вы можете выполнить скрипт, чтобы получить время выполнения merge_sort :
По сравнению с пузырьковой сортировкой и сортировкой вставкой реализация сортировки слиянием чрезвычайно быстра, сортируя массив из десяти тысяч элементов менее чем за секунду!
Преимущества и недостатки сортировки слиянием
Благодаря вычислительной сложности выполнения O(n \log
При сортировке списка из десяти элементов как пузырьковая сортировка, так и сортировка вставкой превосходят сортировку слиянием. Другим недостатком сортировки слиянием является то, что он создает копии массива при рекурсивном вызове себя. Он также создает новый список внутри merge() для сортировки и возврата обеих входных половин. Это заставляет сортировку слиянием использовать гораздо больше памяти, чем пузырьковую сортировку и сортировку вставкой, которые могут сортировать список по месту. Из-за этого ограничения вы можете не использовать сортировку слиянием для сортировки больших списков на оборудовании с ограниченным объемом памяти.
Алгоритм быстрой сортировки в Python
Быстрая сортировка в Python
Вот довольно компактная реализация быстрой сортировки:
Вот краткое изложение кода:
Вот иллюстрация шагов, которые выполняет быстрая сортировка для сортировки массива [8, 2, 6, 4, 5] :
Алгоритм быстрой сортировки
Выбор pivot элемента
Оценка сложности «О»‑большое быстрой сортировки
Оценка времени выполнения быстрой сортировки
К настоящему времени вы знакомы с процессом определения времени выполнения алгоритма. Просто измените название алгоритма в строке 8 :
Вы можете выполнить скрипт так же, как раньше:
Мало того, что быстрая сортировка завершается менее чем за одну секунду, она также намного быстрее сортировки слиянием ( 0.11 секунды против 0.61 секунд). Увеличение количества элементов, указанных ARRAY_LENGTH в 10,000 к 1,000,000 и запустить скрипт снова заканчивается сортировка слиянием окончания в 97 секундах, в то время как быстрая сортировка сортирует список в считанные 10 секунды.
Преимущества и недостатки быстрой сортировки
Результаты показывают, что быстрая сортировка также платит цену рекурсии, когда список достаточно мал, для его завершения требуется больше времени, чем для сортировки вставкой и пузырьковой сортировки.
Алгоритм Timsort в Python
Timsort алгоритм считается гибридным алгоритм сортировки, поскольку он использует лучшие в обоих миров сочетание вставки сортировки и сортировки слиянием. Timsort является близким и дорогим сообществу Python, потому что он был создан Тимом Питерсом в 2002 году для использования в качестве стандартного алгоритма сортировки языка Python. Главная особенность Timsort заключается в том, что он использует преимущества уже отсортированных элементов, которые существуют в большинстве реальных наборов данных. Это называется естественным бегом. Затем алгоритм перебирает список, собирая элементы в прогоны и объединяя их в один отсортированный список.
Реализация Timsort в Python
В этом разделе вы создадите базовую реализацию Python, которая иллюстрирует все части алгоритма Timsort. Если вы заинтересованы, вы можете также проверить первоначальную реализацию C в Timsort. Первым шагом в реализации Timsort является изменение реализации insertion_sort() ранее:
Хотя реализация немного сложнее, чем предыдущие алгоритмы, мы можем кратко изложить ее следующим образом:
Оценка сложности «О»‑большое Timsort
Оценка времени выполнения Timsort
Вы можете использовать, run_sorting_algorithm() чтобы увидеть, как Timsort выполняет сортировку массива из десяти тысяч элементов:
Теперь выполните скрипт, чтобы получить время выполнения timsort :
В 0.51 считанные секунды эта реализация Timsort на полные 0.1 секунды, или на процентов, быстрее сортировки слиянием, хотя и не соответствует 0.11 быстрой сортировке. Это также на 000 процентов быстрее, чем сортировка вставок! Теперь попробуйте отсортировать уже отсортированный список, используя эти четыре алгоритма, и посмотрите, что произойдет. Вы можете изменить свой __main__ раздел следующим образом:
Если вы сейчас выполните скрипт, то все алгоритмы будут запущены и выведут соответствующее время выполнения:
На этот раз Timsort набирает на тридцать семь процентов быстрее, чем сортировка слиянием, и на пять процентов быстрее, чем быстрая сортировка, что позволяет ему использовать преимущества уже отсортированных прогонов. Обратите внимание, что Timsort извлекает выгоду из двух алгоритмов, которые работают намного медленнее, чем сами по себе. Гений Timsort заключается в объединении этих алгоритмов и использовании их сильных сторон для достижения впечатляющих результатов.
Преимущества и недостатки Timsort
Заключение
Сортировка является важным инструментом в любом наборе инструментов Pythonista. Обладая знаниями о различных алгоритмах сортировки в Python и о том, как максимально использовать их потенциал, вы готовы внедрять более быстрые и эффективные приложения и программы! В этом уроке вы узнали:
Вы также узнали о различных методах, таких как рекурсия, разделяй и властвуй и рандомизация. Это фундаментальные строительные блоки для решения длинного списка различных алгоритмов, и они будут появляться снова и снова, пока вы продолжаете исследовать. Возьмите код, представленный в этом руководстве, создайте новые эксперименты и изучите эти алгоритмы. Еще лучше, попробуйте реализовать другие алгоритмы сортировки в Python. Список обширен, но выбор сортировки, пирамидальная сортировка, и дерево рода три отличные варианты, чтобы начать с.