Сортировка вставками на питоне
Хотел разобраться с сортировкой вставками на питоне. Сам я реализовал на питоне такой код:
def InsertionSort(A):
for j in range(1, len(A)):
key = A[j]
i = j - 1
while A[i] > key and i >= 0:
A[i + 1], A[i] = A[i], A[i + 1]
i -= 1
return A
, то есть просто через обмен переменных значениями. Но в интернете везде код примерно такой:
def InsertionSort(A):
for j in range(1, len(A)):
key = A[j]
i = j - 1
while i >= 0 and A[i] > key:
A[i + 1] = A[i]
i -= 1
A[i + 1] = key
return A
Так вот назрел вопрос: можно ли первый код считать алгоритмом сортировки вставкой или же это немного другое?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Нет, первый код - разновидность сортировки пузырьком (элемент ползёт на свое место, обмениваясь с каждым встречным).
В сортировке вставками выполняются "полуобмены" - т.е. элемент извлекается, бОльшие сдвигаются на одну позицию, элемент вставляется - один раз. При этом операций присвоения в среднем меньше получается.