0

Хотел разобраться с сортировкой вставками на питоне. Сам я реализовал на питоне такой код:

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

Так вот назрел вопрос: можно ли первый код считать алгоритмом сортировки вставкой или же это немного другое?

0

1 ответ 1

1

Нет, первый код - разновидность сортировки пузырьком (элемент ползёт на свое место, обмениваясь с каждым встречным).

В сортировке вставками выполняются "полуобмены" - т.е. элемент извлекается, бОльшие сдвигаются на одну позицию, элемент вставляется - один раз. При этом операций присвоения в среднем меньше получается.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.