Метод простого включення

Нехай є масив ключів а[1], а[2],..., а[n]. Для кожного елемента масиву, починаючи з другого, здійснюється порівняння з елементами з меншим індексом (елемент а[і] послідовно порівнюється з елементами а[і-1], а[і-2]...) і до тих пір, поки для чергового елемента a[j] виконується співвідношення а[j]> а[і], а[і] і a[j] міняються місцями. Якщо вдається зустріти такий елемент a[j], що a[j]<= a[i], або якщо досягнута нижня межа масиву, здійснюється перехід до опрацювання елемента a[i+1] (поки не буде досягнута верхня межа масиву) (рисунок 14).

Рисунок 14 – Блок-схема сортування методом включення

Можна побачити, що в кращому разі (коли масив вже впорядкований) для виконання алгоритму з масивом із n елементів буде треба n-1 порівняння і 0 пересилань. У гіршому разі (коли масив впорядкований у зворотному порядку) буде треба n*(n-1)/2 порівнянь і стільки ж пересилань. Отже, можна оцінювати складність методу простих включень як Θ (n²).

Можна скоротити кількість порівнянь, що використовуються в методі простих включень, якщо скористатися тим фактом, що при опрацюванні елемента масиву а[і] елементи а[1], а[2],..., a[i-1] вже впорядковані, і скористатися для пошуку елементу, з яким має виконуватись перестановка, методом двійкового розподілу. У цьому випадку оцінка кількості необхідних порівнянь стає Θ (nlog n). Зазначимо, що оскільки при виконанні перестановки потрібне зсування на один елемент декількох елементів, то оцінка кількості пересилань залишається Θ (n²)..

Void sort_vstavka()

{

Int I,j; int a[50], a1;

Int k[50];

i=0;

while(i<50)

{

for (j=i-1; j>=0; j—)

{

if (a[j]>a[i])

{

a1=a[j];

a[j]=a[i];

a[i]=a1; i--;

}

}

i++;

}

}

Таблиця 1 – Приклад сортування методом простого включення.

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	8 23 5 65 44 33 1 6
Крок 2	8 5 23 65 44 33 1 6
5 8 23 65 44 33 1 6
Крок 3	5 8 23 65 44 33 1 6
Крок 4	5 8 23 44 65 33 1 6
Крок 5	5 8 23 44 33 65 1 6
5 8 23 33 44 65 1 6
Крок 6	5 8 23 33 44 1 65 6
5 8 23 33 1 44 65 6
5 8 23 1 33 44 65 6
5 8 1 23 33 44 65 6
5 18 23 33 44 65 6
15 8 23 33 44 65 6
Крок 7	1 5 823 33 446 65
1 5 8 23 33 6 44 65
1 5 8 23 6 33 44 65
15 8 6 23 33 44 65
15 6 8 23 33 44 65

2 Сортування шляхом підрахунку

Кожний елемент порівнюється зі всіма іншими; остаточно положення елементів визначаються після підрахунку кількості менших ключів.

Треба знайти перестановку р(1) р(2)...р(n), таку, що

Кр(1)<=Кр(2)<=...<=Кр(n).

Метод заснований на тому що j-ключ впорядкованої послідовності перевищує рівно j-1 інших ключів. Ідея полягає в тому, щоб зрівняти попарно всі ключі і підрахувати, скільки з них менші від кожного окремого ключа.

Спосіб виконання поставленого завдання такий:

((порівняти Кj із Кі) при l<=j<i) при 1<i<=N.

Void sort_pidr()

{

int i,j; int a[50], a1[50];

int k[50];

for (i=0; i<50; i++)

k[i]=0;

for(i=0;i<50-1; i++)

for (j=i+1;j<50;j++)

if(a[i]<a[j])

k[i]++;

else k[j]++;

for (i=0; i<50; i++)

a1[k[i]]=a[i];

for (i=0; i<50; i++)

a[i]=a1[i];

}