Алгоритм сортировки вставками

Как и в случае с сортировкой выборкой, алгоритм сортировки вставками выполняет сегментацию списка на 2 части: сортированную и несортированную. Далее алгоритм перебирает 2-й сегмент, вставляя текущий элемент в правильную позицию 1-го сегмента.

Описание алгоритма

По умолчанию предполагается, что 1-й элемент списка отсортирован. Следовательно, можно переходить к следующему элементу, обозначив его х. Когда х больше первого, всё остаётся на своих местах. Когда меньше, первый элемент копируется на 2-ю позицию, а в качестве первого элемента устанавливается, соответственно, х.

Таким образом, при переходе к другим элементам неотсортированного сегмента, происходит перемещение более крупных элементов по списку вверх, пока не закончится список или не встретится элемент, который меньше x. В последнем случае x будет помещено на правильную позицию.

Реализация алгоритма

Реализация алгоритма на языке программирования Python выглядит следующим образом:

def insertion_sort(nums):  
    # Сортировка начинается со 2-го элемента, так как по умолчанию считается, что 1-й элемент уже отсортирован
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        # Сохраняется ссылка на индекс предыдущего элемента
        j = i - 1
        # Элементы сортированного сегмента перемещаются вперёд, если они больше, чем элемент для вставки
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        # Вставляется элемент
        nums[j + 1] = item_to_insert

# Происходит проверка работоспособности
random_list_of_nums = [9, 1, 15, 28, 6]  
insertion_sort(random_list_of_nums)  
print(random_list_of_nums)

Время сортировки вставками

Время сортировки с использованием этого алгоритма, как правило, равняется O(n²), где n — число элементов списка.

Источник — «Sorting Algorithms in Python».