Анализ эффективности двух различных реализаций вставки сортировки

Question

Я придумал две реализации для простого алгоритма сортировки вставкой в ​​Python. Мой вопрос: является ли вторая реализация более эффективной, чем первая? Поскольку в первой реализации кажется, что для каждой итерации while l oop программе необходимо выполнить два назначения: list[i] присваивается list[i-1] и наоборот (кроме уменьшения i на 1 ).

def insertion1(list):

    for i in range(1,len(list)):     

        while i >= 1 and list[i] < list[i-1]:
            list[i],list[i-1] = list[i-1],list[i]
            i -= 1

Но во второй реализации программа должна делать только одно назначение для каждой итерации, в то время как l oop: list[index + 1] = list[index] (опять-таки, кроме уменьшения index на 1 и одного дополнительного назначения после окончания времени l oop: list[index + 1] = temp).

def insertion2(list):

    for i in range(1,len(list)):
        temp = list[i]
        index = i - 1

        while index >= 0 and list[index] > temp:
            list[index + 1] = list[index]
            index -= 1
        list[index + 1] = temp

Значит ли это, что insertion1 примерно должен вдвое увеличить количество операторов присваивания по сравнению с insertion2, что делает insertion2 более точной реализацией сортировки вставкой?

Answer 1

Ваши рассуждения верны. Однако даже insertion2 является неоптимальным. Внутренний l oop выполняет 2 сравнения за итерацию (index >= 0 и list[index] > temp). Это можно уменьшить до (почти) одного сравнения:

    if temp < list[0]:
        # We don't care about values anymore. Every element shall be shifted.
        while index >= 0:
            list[index + 1] = list[index]
            index -= 1
    else:
        # We don't care about indices anymore. list[0] is a natural sentinel
        while temp < list[index]:
            list[index + 1] = list[index]
            index -= 1
    list[index] = temp