сортировка вставками python код
Сортировка вставки в Python [Программа, алгоритм, Пример]
Сортировка вставки в Python-это еще один простой алгоритм сортировки, который можно использовать для сортировки любой линейной структуры данных, такой как список или связанный список.
Сортировка вставки в Python [Программа, алгоритм, Пример]
Помните, как вы в детстве раскладывали карты? Сначала вы выбираете одну карту, затем выбираете следующую карту и кладете ее после первой карты, если она больше, или перед первой картой, если она меньше. затем вы выбираете другую карту и вставляете ее в нужное место. Это один из наиболее распространенных примеров типа вставки. Вы можете легко реализовать сортировку вставки в python, потому что python поставляется с множеством различных функций, каждая из которых построена специально для того, чтобы добавить больше универсальности интерфейсу, чем раньше.
Сортировка вставки в Python-это еще один простой алгоритм сортировки, который можно использовать для сортировки любой линейной структуры данных, такой как список или связанный список. По простоте это похоже на сортировку пузырьков, и это также довольно близко к тому, как люди вручную сортируют что-то (например, руку игральных карт). Как следует из названия, Сортировка вставки основана на вставке элемента в отсортированном списке.
Что такое Сортировка вставки в Python: Обзор
В технике сортировки вставки мы начинаем со второго элемента. Затем сравните его с первым элементом и поместите в нужное место. Затем мы выполняем этот процесс для последующих элементов.
Мы сравниваем каждый элемент со всеми его предыдущими элементами и помещаем или вставляем элемент в его правильное положение. Метод сортировки вставки более выполним для списков с меньшим количеством элементов. Он также полезен для сортировки связанных списков в Python.
Работа сортировки вставки в Python
Сортировка вставки сравнивает первые два элемента.
Он обнаруживает, что и 14, и 33 уже находятся в порядке возрастания. На данный момент 14 находится в отсортированном подсписке.
Сортировка вставки продвигается вперед и сравнивает 33 с 27.
И обнаруживает, что 33 находится не в правильном положении.
Он меняет 33 на 27. Он также проверяет все элементы отсортированного подсписка. Здесь мы видим, что сортированный подсписок имеет только один элемент 14, а 27 больше 14. Следовательно, сортированный подсписок остается отсортированным после замены.
К настоящему времени у нас есть 14 и 27 в отсортированном подсписке. Затем он сравнивает 33 с 10.
Эти значения не упорядочены.
Поэтому мы меняем местами элементы списка.
Однако свопинг делает 27 и 10 несортированными.
Следовательно, мы тоже меняем их местами.
Снова мы находим 14 и 10 в несортированном порядке.
Мы снова меняем их местами. К концу третьей итерации у нас есть сортированный подсписок из 4 пунктов.
Этот процесс продолжается до тех пор, пока все несортированные значения не будут покрыты отсортированным подсписком. Теперь мы рассмотрим некоторые аспекты программирования типа вставки.
Итак, в заключение о том, как работает сортировка вставки в Python, мы можем сказать, что сравнивает текущий элемент с элементами в левой части (сортированный список). Если текущий элемент больше всех элементов на его левой стороне, то он оставляет элемент на своем месте и переходит к следующему элементу. В противном случае он находит свое правильное положение и перемещает его в это положение, перемещая все элементы, которые больше текущего элемента, в отсортированном списке на одну позицию вперед.
Итак, в заключение о том, как работает сортировка вставки в Python, мы можем сказать, что сравнивает текущий элемент с элементами в левой части (сортированный список). Если текущий элемент больше всех элементов на его левой стороне, то он оставляет элемент на своем месте и переходит к следующему элементу. В противном случае он находит свое правильное положение и перемещает его в это положение, перемещая все элементы, которые больше текущего элемента, в отсортированном списке на одну позицию вперед.
Псевдокод
Ниже приведен псевдокод Сортировки вставки для списка с нулевой индексацией:
Реализация сортировки вставки
Реализация алгоритма сортировки вставки в языке программирования Python.
В приведенном выше коде python у нас есть список, содержащий 10 несортированных чисел для сортировки. В первом цикле while мы выполняем итерацию от 2-го элемента так, чтобы первый элемент списка стал первым элементом отсортированного списка. Первый цикл while выбирает элемент из несортированного списка, а второй цикл while (вложенный в первый) сравнивает его с элементами отсортированного списка, если выбранный элемент меньше соседнего левого элемента (отсортированной части), то левый элемент сдвигается на место текущего элемента и текущий элемент копируется на место левого элемента. Последний цикл while, наконец, отображает отсортированный список.
Анализ Сложности
Из псевдокода и приведенной выше иллюстрации следует, что сортировка вставки является эффективным алгоритмом по сравнению с пузырьковой сортировкой или сортировкой выбора. Вместо использования цикла for и текущих условий он использует цикл while, который больше не выполняет никаких дополнительных шагов при сортировке списка.
Таким образом, различные сложности для метода сортировки вставки приведены ниже:
| Таким образом, различные сложности для метода сортировки вставки приведены ниже: | O(n2) |
| В лучшем случае временная сложность | O(n) |
| Средняя временная сложность | O(n2) |
| Сложность пространства | O(1) |
Несмотря на эти сложности, мы все еще можем сделать вывод, что сортировка вставки является наиболее эффективным алгоритмом по сравнению с другими методами сортировки, такими как Пузырьковая сортировка и сортировка выбора.
Характеристики сортировки вставки
Записи
Реальный пример сортировки вставки
Когда мы играем в карты, каждый раз, когда мы берем новую карту и вставляем ее в нужное место, это логика вставки.
Должен Читать
Как преобразовать строку в нижний регистр в PythonКак вычислить квадратный корень в PythonPython User Input | Python Input () Function | Keyboard InputЛучшая книга для изучения Python в 2020 годуPython Reverse List Using reverse() reversed() and Slicing
Вывод
Действительно, он не так хорош, как quicksort, heap sort или mergesort для сортировки больших списков, но он достаточно хорош для сортировки небольших целочисленных списков, где стоимость сравнения невелика.
Insertion Sort Python – это очень простой, в целом неэффективный алгоритм, который, тем не менее, имеет несколько специфических преимуществ, которые делают его актуальным даже после разработки многих других, в целом более эффективных алгоритмов.
Он остается отличным алгоритмом для введения будущих разработчиков программного обеспечения в мир алгоритмов сортировки и до сих пор используется на практике для конкретных сценариев, в которых он блистает.
Топ-5 алгоритмов сортировки на Python
Сортировка — это навык, которым должен обладать каждый программист. Не только для прохождения собеседований, но и для понимания дисциплины в целом. Разные алгоритмы сортировки — отличная демонстрация того, как внутренняя логика может влиять на сложность, скорость и эффективность программы.
Разберем 5 самых распространенных алгоритмов и реализуем их в Python.
Bubble Sort (пузырьковая сортировка)
Этот вид сортировки изучают в начале знакомства с дисциплиной Computer Science, поскольку он максимально просто демонстрирует саму концепцию сортировки.
При этом подходе осуществляется перебор по списку и сравнение соседних элементов. Они меняются местами в том случае, если порядок неправильный. Так продолжается до тех пор, пока все элементы не расположатся в нужном порядке. Из-за большого количества повторений у пузырьковой сортировки его сложность в худшем случае — O(n^2).
Selection Sort (сортировка выбором)
Сортировка выбором — также простой алгоритм, но более эффективный по сравнению с пузырьковой сортировкой. В большинстве случаев сортировка выбором будет более удачным выбором из двух.
В этом алгоритме список (или массив) делится на две части: список с отсортированными элементами и список с элементами, которые только нужно сортировать. Сначала ищется самый маленький элемент во втором. Он добавляется в конце первого. Таким образом алгоритм постепенно формирует список от меньшего к большему. Так происходит до тех пор, пока не будет готовый отсортированный массив.
Insertion Sort (сортировка вставками)
Сортировка вставками быстрее и проще двух предыдущих. Именно так большинство людей тасует карты любой игре. На каждой итерации программа берет один из элементов и подыскивает для него место в уже отсортированном списке. Так происходит до тех пор, пока не останется ни одного неиспользованного элемента.
Merge Sort (сортировка слиянием)
Сортировка слиянием — элегантный пример использования подхода «Разделяй и властвуй». Он состоит из двух этапов:
Quick Sort (быстрая сортировка)
Как и сортировка слиянием, быстрая сортировка использует подход «Разделяй и властвуй». Алгоритм чуть сложнее, но в стандартных реализациях он работает быстрее сортировки слиянием, а его сложность в худшем случае редко достигает O(n^2). Он состоит из трех этапов:
Алгоритмы сортировки на Python
В этой статье мы вкратце расскажем, какие есть основные алгоритмы сортировки и каковы их главные характеристики. Также по каждому алгоритму покажем реализацию на Python.
Искусство наведения порядка
Сортировка означает размещение элементов в определенном порядке. Этот конкретный порядок определяется свойством сравнения элементов. В случае целых чисел мы говорим, что сначала идет меньшее число, а потом — большее.
Расположение элементов в определенном порядке улучшает поиск элемента. Следовательно, сортировка широко используется в информатике.
В данной статье мы рассмотрим обычные алгоритмы сортировки и их реализации на Python. Для сравнения их производительности мы будем рассматривать задачу с сайта Leetcode о сортировке массива. Размеры данных этой задачи ограничены следующим образом:
Мы решили эту задачу при помощи всех известных алгоритмов сортировки. Вот какие у нас получились результаты:
Сортировка методом пузырька
Это самый простой алгоритм сортировки. В процессе его выполнения мы перебираем наш список и на каждой итерации сравниваем элементы попарно. При необходимости элементы меняются местами, чтобы больший элемент отправлялся в конец списка.
Сортировка выбором
В этом алгоритме мы создаем два сегмента нашего списка: один отсортированный, а другой несортированный.
В процессе выполнения алгоритма мы каждый раз удаляем самый маленький элемент из несортированного сегмента списка и добавляем его в отсортированный сегмент. Мы не меняем местами промежуточные элементы. Следовательно, этот алгоритм сортирует массив с минимальным количеством перестановок.
Сортировка вставками
Подобно алгоритму сортировки выбором, мы делим наш список на две части. Далее мы перебираем неотсортированную часть и вставляем каждый элемент из данного сегмента на его правильное место в отсортированной части списка.
Марк Лутц «Изучаем Python»
Скачивайте книгу у нас в телеграм
Сортировка Шелла
Сортировка Шелла является оптимизированным вариантом сортировки вставками.
Оптимизация достигается путем сравнения не только соседних элементов, но и элементов на определенном расстоянии, которое в течении работы алгоритма уменьшается. На последней итерации это расстояние равно 1. После этого алгоритм становится обычным алгоритмом сортировки вставками, что гарантирует правильный результат сортировки.
Но следует отметить один момент: к тому времени, когда это произойдет, наш массив будет почти отсортирован, поэтому итерации будут выполнятся очень быстро.
Пирамидальная сортировка («сортировка кучей»)
Как и в двух предыдущих алгоритмах, мы создаем два сегмента списка: отсортированный и несортированный.
В данном алгоритме для эффективного нахождения максимального элемента в неотсортированной части списка мы используем структуру данных «куча».
Метод heapify в примере кода использует рекурсию для получения элемента с максимальным значением на вершине.
Сортировка слиянием
Этот алгоритм работает по принципу «разделяй и властвуй».
Здесь мы делим список ровно пополам и продолжаем это делать, пока в нем не останется только один элемент. Затем мы объединяем уже упорядоченные части нашего списка. Мы продолжаем это делать, пока не получим отсортированный список со всеми элементами несортированного входного списка.
Быстрая сортировка
В этом алгоритме мы разбиваем список при помощи опорного элемента, сортируя значения вокруг него.
В нашей реализации мы выбрали опорным элементом последний элемент массива. Наилучшая производительность достигается тогда, когда опорный элемент делит список примерно пополам.
Сортировка подсчетом
Этот алгоритм не производит сравнение элементов. Для сортировки используются математические свойства целых чисел. Мы подсчитываем вхождения числа в массиве и сохраняем результат во вспомогательном массиве, где индексу соответствует значение ключа.
Следует также упомянуть поразрядную сортировку, которая использует сортировку подсчетом либо блочную (корзинную) сортировку в качестве подпрограммы. Этот метод сортировки заслуживает отдельной статьи для разбора.
Для удобства соберем весь наш код вместе:
Мы нашли потрясающий плейлист, в котором алгоритмы сортировки демонстрируются при помощи народного танца. Посмотрите это видео, оно того стоит!
В нашем небольшом исследовании мы изучили различные алгоритмы сортировки и определили время их выполнения, а также их потребности в памяти. Теперь мы понимаем, что значит время выполнения, стабильность алгоритма и используемая память. Чтобы выбрать подходящий алгоритм, мы должны оценивать эти параметры. Также, для создания более эффективных решений, типа Timsort, мы можем комбинировать наши базовые алгоритмы.
Сортировки вставками
Общая суть сортировок вставками такова:
Самое слабое место в этом подходе — вставка элемента в отсортированную часть массива. На самом деле это непросто и на какие только ухищрения не приходится идти, чтобы выполнить этот шаг.
Сортировка простыми вставками
Проходим по массиву слева направо и обрабатываем по очереди каждый элемент. Слева от очередного элемента наращиваем отсортированную часть массива, справа по мере процесса потихоньку испаряется неотсортированная. В отсортированной части массива ищется точка вставки для очередного элемента. Сам элемент отправляется в буфер, в результате чего в массиве появляется свободная ячейка — это позволяет сдвинуть элементы и освободить точку вставки.
На примере простых вставок показательно смотрится главное преимущество большинства (но не всех!) сортировок вставками, а именно — очень быстрая обработка почти упорядоченных массивов:
При таком раскладе даже самая примитивная реализация сортировки вставкам, скорее всего, обгонит супер-оптимизированный алгоритм какой-нибудь быстрой сортировки, в том числе и на больших массивах.
Этому способствует сама основная идея этого класса — переброска элементов из неотсортированной части массива в отсортированную. При близком расположении близких по величине данных место вставки обычно находится близко к краю отсортированной части, что позволяет вставлять с наименьшими накладными расходами.
Сортировка простыми вставками с бинарным поиском
Так как место для вставки ищется в отсортированной части массива, то идея использовать бинарный поиск напрашивается сама собой. Другое дело, что поиск места вставки не является критичным для временно́й сложности алгоритма (главный пожиратель ресурсов — этап самой вставки элемента в найденную позицию), поэтому данная оптимизация здесь мало что даёт.
А в случае почти отсортированного массива бинарный поиск может работать даже медленнее, поскольку он начинает с середины отсортированного участка, который, скорее всего, будет находиться слишком далеко от точки вставки (а на обычный перебор от позиции элемента до точки вставки уйдёт меньше шагов, если данные в массиве в целом упорядочены).
В защиту бинарного поиска отмечу, что он может сказать решающее слово в эффективности других сортировок вставками. Благодаря ему, в частности, на среднюю сложность по времени выходят такие алгоритмы как сортировка библиотекаря и пасьянсная сортировка. Но про них позже.
Па́рная сортировка простыми вставками
Модификация простых вставок, разработанная в тайных лабораториях корпорации Oracle. Эта сортировка входит в пакет JDK, является составной частью Dual-Pivot Quicksort. Используется для сортировки малых массивов (до 47 элементов) и сортировки небольших участков крупных массивов.
В буфер отправляются не один, а сразу два рядом стоя́щих элемента. Сначала вставляется больший элемент из пары и сразу после него метод простой вставки применяется к меньшему элементу из пары.
Что это даёт? Экономию для обработки меньшего элемента из пары. Для него поиск точки вставки и сама вставка осуществляются только на той отсортированной части массива, в которую не входит отсортированная область, задействованная для обработки большего элемента из пары. Это становится возможным, поскольку больший и меньший элементы обрабатываются сразу друг за другом в одном проходе внешнего цикла.
На среднюю сложность по времени это не влияет (она так и остаётся равной однако па́рные вставки работают чуть быстрее чем обычные.
Алгоритмы я иллюстрирую на Python, но тут приведу первоисточник (видоизменённый в целях читабельности) на Java:
Сортировка Шелла
В этом алгоритме очень остроумный подход в определении того, какую именно часть массива считать отсортированной. В простых вставках все просто: от текущего элемента всё что слева — уже отсортировано, всё что справа — ещё не отсортировано. В отличие от простых вставок сортировка Шелла не пытается слева от элемента сразу формировать строго отсортированную часть массива. Она создаёт слева от элемента почти отсортированную часть массива и делает это достаточно быстро.
Сортировка Шелла закидывает текущий элемент в буфер и сравнивает его с левой частью массива. Если находит бо́льшие элементы слева, то сдвигает их вправо, освобождая место для вставки. Но при этом берёт не всю левую часть, а только некоторую группу элементов из неё, где элементы разнесены друг от друга на некоторое расстояние. Такая система позволяет быстро вставлять элементы примерно в ту область массива, где они должны находиться.
С каждой итерацией основного цикла это расстояние постепенно уменьшается и когда оно становится равным единице, то сортировка Шелла в этот момент превращается в классическую сортировку простыми вставками, которой дали на обработку почти отсортированный массив. А почти отсортированный массив сортировка вставками в полностью отсортированный преобразует быстро.
Про сортировку Шелла написано несколько хабрастатей, поэтому не будем перегружаться информацией и двигаемся дальше.
Сортировка деревом
Сортировка деревом за счёт дополнительной памяти быстро решает вопрос с добавлением очередного элемента в отсортированную часть массива. Причём в роли отсортированной части массива выступает бинарное дерево. Дерево формируется буквально на лету при переборе элементов.
Элемент сравнивается сначала с корнем, а потом и с более вложенными узлами по принципу: если элемент меньше чем узел — то спускаемся по левой ветке, если не меньше — то по правой. Построенное по такому правилу дерево затем можно легко обойти так, чтобы двигаться от узлов с меньшими значениями к узлам с большими значениями (и таким образом получить все элементы в возрастающем порядке).
Основная загвоздка сортировок вставками (затраты на вставку элемента на своё место в отсортированной части массива) здесь решена, построение происходит вполне оперативно. Во всяком случае для освобождения точки вставки не нужно медленно передвигать караваны элементов как в предыдущих алгоритмах. Казалось бы, вот она, наилучшая из сортировок вставками. Но есть проблема.
Когда получается красивая симметричная ёлочка (так называемое идеально сбалансированное дерево) как в анимации тремя абзацами выше, то вставка происходит быстро, поскольку дерево в этом случае имеет минимально возможную вложенность уровней. Но сбалансированная (или хотя бы близкая к таковой) структура из рандомного массива получается редко. И дерево, скорее всего, будет неидеальное и несбалансированное — с перекосами, заваленным горизонтом и избыточным количеством уровней.
Рандомный массив со значениями от 1 до 10. Элементы в таком порядке генерируют несбалансированное двоичное дерево:
Дерево мало построить, его ещё нужно обойти. Чем больше несбалансированности — тем сильнее будет буксовать алгоритм по обходу дерева. Тут как скажут звёзды, рандомный массив может породить как уродливую корягу (что более вероятно) так и древовидный фрактал.
Значения элементов те же, но порядок другой. Генерируется сбалансированное двоичное дерево:
На прекрасной сакуре
Не хватает лепестка:
Бинарное дерево из десятки.
Проблему несбалансированных деревьев решает сортировка выворачиванием, которая использует особую разновидность бинарного дерева поиска — splay tree. Это замечательное древо-трансформер, которое после каждой операции перестраивается в сбалансированное состояние. Про это будет отдельная статья. К тому времени подготовлю и реализации на Python как для Tree Sort, так и для Splay sort.
Ну чтож, мы кратенько прошлись по самым популярным сортировкам вставками. Простые вставки, Шелл и двоичное дерево мы все знаем ещё со школы. А теперь рассмотрим других представителей этого класса, не столь широко известных.
Сортировка вставкой в Python
Сортировка вставкой в Python – это простой и более эффективный алгоритм, чем алгоритм пузырьковой сортировки. Концепция основана на принципе колоды карт, в которой мы сортируем игральные карты в соответствии с конкретной картой. У этого метода есть много преимуществ, но есть много эффективных алгоритмов, доступных в структуре данных.
Играя в карты, мы сравниваем расположение карт в своих руках с другими игроками. Большинству игроков нравится сортировать карты в порядке возрастания, чтобы они могли быстро увидеть, какие комбинации есть в их распоряжении.
Реализация сортировки вставкой легка и проста, потому что ей обычно учат на начальном уроке программирования. Это стабильный алгоритм на месте, который более полезен для небольшого числа или частично отсортированных элементов.
Этот алгоритм не такой быстрый, потому что он использует вложенный цикл для сортировки элементов.
Давайте разберемся в следующих терминах.
Что означает “на месте” и “стабильно”?
Что более важно, сортировка вставкой в Python не требует заранее знать размер массива, и она получает по одному элементу за раз.
В сортировке вставкой замечательно то, что если мы вставляем больше элементов для сортировки, алгоритм размещает их в нужном месте, не выполняя полную сортировку.
Это более эффективно для массива небольшого (менее 10) размера. Теперь давайте разберемся с концепцией сортировки вставкой.
Концепция сортировки вставкой
Массив разделился практически на две части при сортировке вставками – несортированная часть и отсортированная часть.
Отсортированная часть содержит первый элемент массива, а другая несортированная часть содержит остальную часть массива. Первый элемент в несортированном массиве сравнивается с отсортированным массивом, чтобы мы могли поместить его в соответствующий подмассив.
Он фокусируется на вставке элементов путем перемещения всех элементов, если правое значение меньше левого.
Это будет повторяться до тех пор, пока весь элемент не будет вставлен в правильное место.
Ниже приведен алгоритм сортировки массива с помощью вставки.
Разберемся в следующем примере.
Рассмотрим первый элемент отсортированного массива.
Первый шаг к добавлению 10 в отсортированный подмассив.
Теперь берем первый элемент из несортированного массива – 4. Это значение сохраняем в новой переменной temp. Теперь мы видим, что 10> 4, перемещаем 10 вправо, и это перезаписывает 4, которые были ранее сохранены.
[10, 10, 25, 1, 5] (темп = 4)
Здесь 4 меньше, чем все элементы в отсортированном подмассиве, поэтому мы вставляем его в первую позицию индекса.
У нас есть два элемента в отсортированном подмассиве.
Теперь проверьте число 25. Мы сохранили его во временной переменной. 25> 10, а также 25> 4, затем мы помещаем его в третью позицию и добавляем в отсортированный подмассив.
Снова проверяем цифру 1. Сохраняем в темп. 1 меньше 25. Он перезаписывает 25.
[4, 10, 25, 25, 5] 10> 1, затем перезаписывается снова
[25, 4, 10, 25, 5] 4> 1 теперь ставим значение temp = 1
Теперь у нас есть 4 элемента в отсортированном подмассиве. 5