4) Метод сортування масивів вставкою та його покращенні методи.

Сортування вставкою − це метод який майже настільки ж простий, що і сортування вибором, але більш гнучкий. Цей метод часто використовують при сортуванні карт: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже відібрали (тим самим залишаючи їх відсортованими).  type Іndex = 0..n; var a: array[1..n] of elem; procedure Іnsert;     var і,j: іndex;     x: elem;     begіn     for і:= 1 to n do     begіn         x:= a[і]; a[0]:= x; j:= і-1;         whіle x.key < a[j].key do         begіn         a[j+1]:= a[j]; j:= j-1;         end;         a[j+1]:= x;     end;     end; Також як і в сортуванні вибором, у процесі сортування елементи зліва від покажчика i знаходяться вже у відсортованому порядку, але вони не обов'язково знаходяться у своїй останній позиції, оскільки їх ще можуть пересунути праворуч щоб вставити більш маленькі елементи, які зустрілись пізніше.. Однак масив стає цілком відсортованим, коли покажчик досягає правого краю. Сортування простими вставками в чомусь схожа на вищевикладений методи сортування вибором. Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином у його початку "виростає" відсортована послідовність... Однак у сортуванні вибором можна було чітко заявити, що на і-м кроці елементи a[0]...a[і] розташовані на остаточних місцях і нікуди більш не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a[0]...a[і] впорядкована. При цьому по ходу алгоритму в нее будуть вставлятися (див. назва методу) все нові елементи. Будемо розбирати алгоритм, розглядаючи його дії на і-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a[0]...a[і] і невпорядковану a[і+1]...a[n]. На наступному, кожному (і+1)-му кроці алгоритму беремо a[і+1] елемент і вставляємо на потрібне місце в готову частину масиву. Пошук придатного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементам, що стоять перед ним. У залежності від результату порівняння елемент або залишається на поточному місці (вставка довершена), або вони міняються місцями і процес повторюється.   Таким чином, у процесі вставки ми "просіваємо" елемент x до початку масиву, зупиняючи у випадку, коли 1.Знайдено елемент, менший x або 2.Досягнутий початок послідовності.  Аналогічно сортуванню вибором, середнє, а також гірше число порівнянь і пересилань оцінюються як Theta (n2), додаткова пам'ять при цьому не використовується. Гарним показником або, краще сказати, перевагою даного методу сортування є те, що : майже відсортований масив буде досортирован дуже швидко. Це, разом із стійкістю алгоритму, робить метод достойним вибором у відповідних ситуаціях. Алгоритм можна дещо поліпшити. Помітимо, що на кожнім кроці внутрішнього циклу перевіряються дві умови. Можна об'єднати їх в одну умову, поставивши в початок масиву спеціальний „сторожовий елемент”. Він повинний бути свідомо менше всіх інших елементів масиву.    Тоді при j=0 буде свідомо вірно a[0] <= x. Цикл зупиниться на нульовому елементі, що і було метою умови j>=0. Таким чином, сортування буде відбуватися вірним чином, а у внутрішньому циклі стане на одне порівняння менше. З обліком того, що воно вироблялося Theta(n2) раз, це - реальна перевага. Однак, відсортований масив буде не повний, тому що з нього зникло перше число. Для закінчення сортування це число варто повернути назад, а потім вставити у відсортовану послідовність a[1]...a[n].  Подальшим розвитком методу сортування вставками є сортування методом Шелла, інша назва сортування вставками зі зменшенням відстані. Ми не будемо описувати алгоритм у загальному виді, а обмежимося випадком, коли число елементів у масиві, який треба відсортувати є ступенем числа 2. Для масиву з 2n елементами алгоритм працює в такий спосіб. На першій фазі відбувається сортування включенням усіх пар елементів масиву, відстань між який дорівнює 2(n-1). На другій фазі виробляється сортування включенням елементів отриманого масиву, відстань між який дорівнює 2(n-2). І так далі, поки ми не дійдемо до фази з відстанню між елементами, рівної одиниці, і не виконаємо завершальне сортування з включеннями. Застосування методу Шелла до массиву наведено в наступному прикладі.  Приклад сортування методом Шелла:  Початковий вигляд масиву 8 23 5 65 44 33 1 6 Фаза 1 (сортуються елементи, відстань між якими дорівнює чотири) 8 23 5 65 44 33 1 6 8 23 5 65 44 33 1 6 8 23 1 65 44 33 5 6 8 23 1 6  44 33 5 65 Фаза 2 (сортуються елементи, відстань між якими дорівнює два) 1 23 8 6  44 33 5  65 1 23 8 6  44 33 5  65 1 23 8 6  5  33 44 65 1 23 5 6  8  33 44 65 1 6  5 23 8  33 44 65 1 6  5 23 8  33 44 65 1 6  5 23 8  33 44 65 Фаза 3 (сортуються елементи, відстань між якими дорівнює одиниці) 1 6 5 23 8  33 44 65 1 5 6 23 8  33 44 65 1 5 6 23 8  33 44 65 1 5 6 8  23 33 44 65 1 5 6 8  23 33 44 65 1 5 6 8  23 33 44 65 1 5 6 8  23 33 44 65

У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з t відстаней між елементами h1, h2, ..., ht, для яких виконуються умови h1 = 1 і h(і+1) < hі. Дональд Кнут показав, що при правильно підібраних t і h складність алгоритму Шелла є O(n(1.2)), що істотно менше складності простих алгоритмів сортування.