Сортировка вставками

Алгоритм, похожий на сортировку карт в руке: берём очередной элемент и вставляем его на правильное место среди уже отсортированных.

Идея алгоритма

Считаем первый элемент уже отсортированным
Берём следующий элемент (key)
Сдвигаем все бóльшие элементы вправо, освобождая место
Вставляем key на освободившееся место
Повторяем для всех оставшихся элементов

Разбор

Внешний цикл

нц для i от 1 до n - 1
    key := A[i]
    j := i - 1
    ...
кц

Начинаем с индекса 1 (первый элемент «уже отсортирован»). Запоминаем текущий элемент в key и будем искать для него правильное место.

Сдвиг элементов

нц пока (j >= 0) и (A[j] > key)
    A[j + 1] := A[j]
    j := j - 1
кц
A[j + 1] := key

Двигаемся влево по отсортированной части. Пока элемент A[j] больше key — сдвигаем его вправо. Когда нашли правильное место (элемент не больше key или дошли до начала) — вставляем key.

Сложность: $O(n^2)$ в худшем случае (массив отсортирован в обратном порядке). Но на почти отсортированных данных работает за $O(n)$ — каждый элемент сдвигается совсем немного.

Полная программа

алг main(цел n)
нач
    если n <= 0 то
        вывод "Размер массива должен быть положительным", нс
        выход
    все

    цел таб A[0:n-1]
    заполнить_случайными(n, A)

    вывод "Исходный массив:", нс
    печать_массива(n, A)

    insertionsort(n, A)

    вывод "Отсортированный массив:", нс
    печать_массива(n, A)
кон

алг insertionsort(цел n, цел таб A[0:n-1])
нач
    цел i, j, key
    нц для i от 1 до n - 1
        key := A[i]
        j := i - 1
        нц пока (j >= 0) и (A[j] > key)
            A[j + 1] := A[j]
            j := j - 1
        кц
        A[j + 1] := key
    кц
кон

алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        A[i] := irnd(100)
    кц
кон

алг печать_массива(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        вывод A[i], " "
    кц
    вывод нс
кон

▶ Запустить пример