Опис алгоритму сортування проста вставка

Основна ідея алгоритму полягаяє в тому що послідовно вибирати елементи з не відсортованого масиву та вставляти їх на свої місця в відсортований масив.

Нехай заданий числовий масив m={m_{0 ,}m_1, m_2,….,m_n}.

Для формування відсортованої послідовності створюється масив r такої ж розмірності , як і масив m. Елемент m₀ масиву m поміщається у нульовому коміру масиву r : r₀=m₀. Індекс k останнього елемента в масиві r встановлюється до нуля : k=0.

Далі з масиву m до його вичерпання ітераційно вибираються елементи m_i (i=1,…,n) починаючи з елемента з індексом i=1; для кожного вибраного елемента m_i в ході однієї ітерації з номером і реалізуються наступні кроки.

Крок 1. Пошук місцезнаходження вибраного елемента. Для елемента m_i ітераційно (j=0,…,k,) починаючи з j=0 шукається місце j вставки в відсортований масив r :

1.1 якщо m_i < r_{i ,} тоді місце вставного елементу m_i комірка вихід з циклу ;

1.2 інакше j=j+1:

якщо j≤k перехід на крок 1.1;

інакше - вихід з циклу.

Місце вставки j елементу m_i знайдено.

Крок 2. Зсув. Якщо на кроці 1 місце вставки в середині циклу не знайшли (j=k+1), отже це місце останнім елементом масиву r, крок 2

виконувати не потрібно,а потрібно тільки тільки вставити елемент на своє місце. Інакше елементи масиву r з індексами j,…,k ітераційно (p=k,…,j), починаючи з найбільшого елемента r_p, p=k, переміщуються на одну позицію вправо :

2.1 записуємо r_p+1=r_p

2.2 припустимо p=p-1

якщо p≥j, перехід на крок 2.1;

інакше – вихід з циклу.

Крок 3. Вставка. Елемент m_i вставляєься на своє місце : r_j=m_i; індекс останнього елемента у відсотковому масиві r збільшується на одиницю,

k=k+1.

Крок 4. Завершення. Припускаємо i=i+1 i: якщо i ≤ n перехід на крок, 1

Інакше сортування завершене, вихід.