Лекция: Принцип методу упорядкування вставлянням

Масив поділяється на дві частини: впорядковану і невпорядковану. Елементи з невпорядкованої частини по черзі вибираються і вставляються в упорядковану частину не порушуючи при цьому впорядкованості елементів. На початку роботи алгоритму до впорядкованої частини масиву відносять тільки перший елемент, а до невпорядкованої – всі інші елементи.

Таким чином, потрібно n-1 раз (n – розмірність масиву) виконати дії:

– вибрати i– й елемент із невпорядкованої частини й зберегти в допоміжній змінній;

– знайти позицію j у впорядкованій частині масиву, в якій вибраний елемент не порушуватиме впорядкованості;

– зсув елементів масиву від i-1– го до j-1– го вправо для звільнення знайденої позиції;

– вставити вибраний елемент у знайдену j- ту позицію.

Схематично описані дії можна подати так: