Автор оригинала: Team Python Pool.

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

1. Если элемент является первым, он уже отсортирован.
2. Перейдите к следующему элементу списка.
3. Сравните текущий элемент со всеми элементами в отсортированном списке.
4. Если элемент в отсортированном списке меньше текущего элемента, выполните итерацию к следующему элементу. В противном случае сдвиньте все большие элементы в списке на одну позицию вправо.
5. Вставьте значение в правильное положение.
6. Повторяйте до тех пор, пока полный список не будет отсортирован.

Псевдокод

Ниже приведен псевдокод Сортировки вставки для списка с нулевой индексацией:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Реализация сортировки вставки

Реализация алгоритма сортировки вставки в языке программирования Python.

list=[10,1,5,0,6,8,7,3,11,4]

while(i<10):
 [i]
 
 +1

  while(j>0 and list[j-1]>element):
   [j-1]
   -1

 

while(i<10):
  print (list[i])
 +1

Выход:

0
1
3
4
5
6
7
8
10
11

Объяснение:

В приведенном выше коде python у нас есть список, содержащий 10 несортированных чисел для сортировки. В первом цикле while мы выполняем итерацию от 2-го элемента так, чтобы первый элемент списка стал первым элементом отсортированного списка. Первый цикл while выбирает элемент из несортированного списка, а второй цикл while (вложенный в первый) сравнивает его с элементами отсортированного списка, если выбранный элемент меньше соседнего левого элемента (отсортированной части), то левый элемент сдвигается на место текущего элемента и текущий элемент копируется на место левого элемента. Последний цикл while, наконец, отображает отсортированный список.

Анализ Сложности

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

Однако, даже если мы передадим сортированный список методу сортировки вставки, он все равно выполнит внешний цикл for, тем самым требуя n шагов для сортировки уже отсортированного списка. Это делает наилучшую временную сложность сортировки вставки линейной функцией N, где N-количество элементов в списке .

Таким образом, различные сложности для метода сортировки вставки приведены ниже:

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

Характеристики сортировки вставки

• Сортировка вставки занимает максимальное время для выполнения в худшем случае, когда заданные входные элементы сортируются в обратном порядке. Это занимает меньше всего времени
• Сортировка вставки следует инкрементальному подходу в достижении своих результатов.
• Это очень предпочтительно, когда количество элементов меньше по количеству и большинство элементов отсортировано.
• Сложность, связанная с сортировкой вставки, может быть уменьшена до O(log n), если метод двоичного поиска используется для поиска его отсортированного списка каждый раз, чтобы соответствующим образом разместить элемент из несортированного числа. Этот процесс можно назвать сортировкой Двоичной вставки.

Записи

• Из-за своей дорогостоящей временной сложности для операций копирования сортировка вставки обычно не используется для сортировки списка.
• Сортировка вставки в Python-это эффективный способ вставить ограниченное количество элементов в уже отсортированный список.
• Этот метод алгоритма более эффективен, чем методы пузырьковой сортировки и сортировки выбора.
• Сортировка вставки в Python менее эффективна, чем другие методы, такие как Быстрая сортировка и сортировка слиянием.

Реальный пример сортировки вставки

Когда мы играем в карты, каждый раз, когда мы берем новую карту и вставляем ее в нужное место, это логика вставки.

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

Должен Читать

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

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

Счастливого кодирования!