Лекция: Принцип методу упорядкування вставлянням
Масив поділяється на дві частини: впорядковану і невпорядковану. Елементи з невпорядкованої частини по черзі вибираються і вставляються в упорядковану частину не порушуючи при цьому впорядкованості елементів. На початку роботи алгоритму до впорядкованої частини масиву відносять тільки перший елемент, а до невпорядкованої – всі інші елементи.
Таким чином, потрібно n-1 раз (n – розмірність масиву) виконати дії:
– вибрати i– й елемент із невпорядкованої частини й зберегти в допоміжній змінній;
– знайти позицію j у впорядкованій частині масиву, в якій вибраний елемент не порушуватиме впорядкованості;
– зсув елементів масиву від i-1– го до j-1– го вправо для звільнення знайденої позиції;
– вставити вибраний елемент у знайдену j- ту позицію.
Схематично описані дії можна подати так: