04.05.2023 в 09:18
Тим Тоуди
Алгоритм сортировки вставки в Python
Простой метод сортировки, известный как “сортировка по вставке”, включает в себя непрерывную вставку элементов в нужные места в отсортированном массиве. Он работает путем многократного обхода массива слева направо, сортируя каждый элемент по мере его прохождения. Это простой для понимания алгоритм, который хорошо работает с небольшими наборами данных.
Как работает сортировка вставками
- Выполните итерацию слева направо по массиву.
- Сравните каждый элемент с предыдущими и поместите его в правильное место в отсортированном подмассиве.
- Он начинается с 1 и сравнивает элемент — 1.
- Сортировка будет продолжаться до тех пор, пока не будут отсортированы все компоненты.
Графическое представление работ по сортировке вставок
где: Comparing - сравнение, Swap - обмен.
Сортировка по вставке
Шаги, которые необходимо предпринять
- Во-первых, вам нужно найти длину массива.
- Вы не должны забывать, что элементы массива сравниваются с предыдущими значениями, поэтому цикл
forдолжен начинаться с 1 до длины списка, а затем вам нужно использовать циклwhileelseдля сравнения элементов массива. - Вам нужно поменять местами, если массив
x-1больше текущего значения массива; в противном случае вам не нужно изменять положение массива. - Возвращаемое значение после сортировки.
app.py
def ins_sort(aray):
len_list = len(aray)
for i in range(1, len_list):
ref_value = aray[i]
x = i
while x>0 and aray[x-1] > ref_value:
aray[x] = aray[x-1]
x -= 1
else:
aray[x] = ref_value
return aray
aray=[6,5,3,1,2]
print("before sort ",aray)
hello=ins_sort(aray)
print("result sorted is ",hello)результат app.py
before sort [6, 5, 3, 1, 2]
result sorted is [1, 2, 3, 5, 6]Далее мы вам предлагаем ознакомиться дополнительными трюками Python для легкого управления списками в ваших проектах.
