Сортування вставкою

Цей алгоритм має яскраво виражений рекурсивний характер. Ідея алгоритму така.

Відокремимо від масиву останній елемент. За допомогою цього ж алгоритму (рекурсивно) відсортуємо скорочений масив (без останнього елемента). У відсортований масив вставимо відділений спочатку останній елемент. Умовою закінчення рекурсії є те, що останній скорочений масив буде містити всього один елемент.

Найважчим в цьому алгоритмі є вставка елемента у відсортований масив. Робиться це так. Масив послідовно проглядається до тих пір, поки не буде виявлене місце, куди треба вставити цей елемент. Потім всі елементи масиву, що знаходяться після цього місця, переміщаються на одну позицію вправо, а елемент, що вставляється, займає звільнене місце.

Програму даного алгоритму зручно представити у вигляді двох загальних процедур: СортуванняВставкою і Вставка (коди 3.10 і 3.11):

Код 3.10

Код 3.11

Hові поняття: