Есть ли разница в способе написания insertion sort?

Question

Являются ли данные способы написания сортировки вставками одинаковыми и работает ли первый "надежнее" чем второй:

def insertion_sort(A:list):
    for top in range(1, len(A)):
        k = top
        while k > 0 and A[k-1] > A[k]:
            A[k], A[k-1] = A[k-1], A[k]
            k -= 1
            print(A)

def insertion_sort_2(A):
    for top in range(1, len(A)):
        while top > 0 and A[top-1] > A[top]:
            A[top], A[top-1] = A[top-1], A[top]
            top -= 1
    print(A)

Answer 1

Оба метода неудачные, они теряют важную деталь реализации сортировки вставками, которая позволяет ускориться - сдвиг части массива, а не полные обмены. Кроме того, во втором методе вы меняете переменную цикла for.

Вот классические вставки:

def insertionSort(A):
    for i in range(1, len(A)):
        top = A[i]
        j = i-1
        while j >= 0 and top < A[j] :
                A[j + 1] = A[j]
                j -= 1
        A[j + 1] = top
    print(A)

БЛОГ НА HUSL

Есть ли разница в способе написания insertion sort?

Ответы (1 шт):