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

For (i=2;i<n;i++)

Вставити елемент mas[i] в упорядковану частину масиву

Операція вставки елемента mas[i] виконується в три кроки, що ми зараз і продемонструємо для і=4.

1. Зберігаємо копію вставляємого числа. В даному прикладі елемент mas[4] копіюємо в mas[0], який ми спеціально для цього і не використовували для запису масиву.

2. Проводимо здвиг вправо елементи, розміщені до mas[i], поки не буде знайдено потрібне місце під вставку елемента. В нашому випадку спочатку потрібно здвинути вправо число 8, а потім - число 5, як показано на рисунку.

3. Помістити нове значення на потрібне місце. Для даного прикладу число 3 вставляємо в масив із mas[0].

Процес просіювання (пошуку потрібного місця для включення елемента x ) може припинитися при виконанні однієї із двох умов :

1) знайдено елемент a j з ключем, меншим ніж ключ у x ;

2) досягнутий лівий кінець "готової" послідовності.

Таким чином програмна реалізація методу прямого включення матиме вигляд (Файл SORT_1.CPP):

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<<mas[i]<<` `;

cout<<endl<<"--------------------------------"<<endl;

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<<endl;

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<<i<<" -element masuvy"<<endl;

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<<endl;

vuv(n);

//Sort_prjamojy vstavkojy

for (int j=2;j<=n;j++)

{

tmp=mas[j]; mas[0]=tmp; i=j;

while (tmp<mas[j-1])

{

mas[j]=mas[j-1];

j--;

}

mas[j]=tmp;

}

cout<<"Masuv vidsortovanuy "<<endl;

vuv(n);

getch();

return 0;

}

Аналіз прямого включення. Кількість порівнянь ключів Ci при i-ому просіюванні найбільше дорівнює i, найменше - 1, а середньоймовірна кількість - i/2. Кількість же перестановок (переприсвоєнь ключів), включаючи бар'єр, Mi=Ci+2. Тому для оцінки ефективності алгоритму у випадках початково впорядкованого, зворотньо впорядкованого та довільного масиву можна скористатися наступними співвідношеннями:

;

;

;

;

;

.

Очевидно, що розглянутий алгоритм описує процес стійкого сортування. Загальна кількість операцій буде рівня (n-1), що відповідатиме при обрахунку кількості операцій O(n2). Тому найгірший час сортування вставками дійсно є квадратичним.

2.2 Сортування бінарним включенням

Алгоритм прямого включення можна значно покращити, якщо врахувати, що "готова" послідовність є вже впорядкованою. Тому можна скористатися бінарним пошуком точки включення в "готову" послідовність. Тобто даний метод містить в собі метод бінарного пошуку елемента (пошук бінарним деревом) в масиві, в даному випадку - місця між елементами, де повинен бути розміщений даний елемент. Тому що пошук місця під наступний елемент можна зобразити як рух по дереву, від "стовбура" до "кореня". На першому кроці ділимо весь відсортований масив навпіл, далі порівнюємо даний елемент із елементами масиву з що посередині, якщо він менший, знову ділимо лівий підмасив, більший - правий. І так до тих пір поки не визначимо місце, де буде знаходитися даний елемент.

{l=1;r=j;tmp=mas[j];

while (l<r)

{

m=(r+l)/2;

if (mas[m]<=tmp) l=m+1; else r=m;

}

Нехай маємо впорядкований масив (8, 9, 10, 16, 18, 20, 35), покажемо жирним рух по бінарному дереву, для знаходження місця елементу = 19.

Програмна реалізація такого модифікованого методу включення матиме вигляд наступної програми (Файл SORT_2.СРР):

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<<mas[i]<<` `;

cout<<endl<<"--------------------------------"<<endl;

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<<endl;

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<<i<<" -element masuvy"<<endl;

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<<endl;

vuv(n);

//Sort_binarn vstavkojy

int l,r,m;

for (int j=2;j<=n;j++)

{l=1;r=j;tmp=mas[j];

while (l<r)

{

m=(r+l)/2;

if (mas[m]<=tmp) l=m+1; else r=m;

}

for (i=j;i>=(r+1);i--) mas[i]=mas[i-1];

mas[r]=tmp;

}

cout<<"Masuv vidsortovanuy "<<endl;

vuv(n);

getch();

return 0;

}

Аналіз бінарного включення. Зрозуміло, що кількість порівнянь у такому алгоритмі фактично не залежить від початкового порядку елементів. Місце включення знайдено, якщо L=R. Отже вкінці пошуку інтервал повинен бути одиничної довжини. Таким чином ділення його пополам на i-ому етапі здійснюється log(i) раз. Тому кількість операцій порівняння буде:

, де , .

Апроксимуючи цю суму інтегралом, отримаємо наступну оцінку :

, де .

Однак істинна кількість порівнянь на кожному етапі може бути більшою ніж log(i) на 1. Тому

.

Нажаль покращення, що породженні введенням бінарного пошуку, стосується лише кількості операцій порівняння, а не кількості потрібних переміщень елементів. Фактично кількість перестановок M залишається величиною порядку N2. Для досить швидких сучасних ЕОМ рух елемента, тобто самого ключа і зв'язаної з ним інформації, займає значно більше часу, ніж порівняння самих ключів. Крім того сортування розглядуваним методом вже впорядкованого масиву за рахунок log(i) операцій порівняння вимагатиме більше часу, ніж у випадку послідовного сортування з прямим включенням. Очевидно, що кращий результат дадуть алгоритми, де перестановка, нехай і на велику відстань, буде пов'язана лише з одним елементом, а не з переміщенням на одну позицію цілої групи.

2.3 Сортування прямим вибором

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

1) на i-ому етапі серед елементів mas[i], mas[i+1],…,mas[n] вибирається елемент з найменшим ключем mas[j]=min ;

2) проводиться обмін місцями mas[j] та mas[i].

Процес послідовного вибору і перестановки проводиться поки не залишиться один єдиний елемент - з самим найбільшим ключем.

Взагалі, існує декілька способів реалізації даного алгоритму. Можна використовувати два масиви і копіювати елементи в потрібному порядку із одного масиву в другий. Проте, це є більш затратний спосіб. Наведемо графічний аналіз реалізації самого методу. Нехай маємо задачу, на прикладі масиву, зображеного нижче. Спробуємо впорядкувати цей масив по зростанню.

На першому кроці переглядаємо весь масив від індексу 1 до індексу n (в даному випадку n=7) з метою пошуку найменшого елемента масиву. Далі беремо цей індекс на кожному кроці записуємо в комірку з індексом 0. По закінченню проходження циклу міняємо елементи з індексом і-початкове та елемент індекс якого записаний у комірці під номером 0.

Дальше переглядаємо масив вже без першого елемента, оскільки ж відомо що в ньому записаний найменший елемент масиву.

Маємо, що мінімальний елемент решти масиву знаходиться в позиції 5, при його пошуку індекс заноситься в комірку з індексом 0. Знову проводимо обмін.

Запишемо саму програму реалізації даного методу (Файл SORT_3.CPP):

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<<mas[i]<<` `;

cout<<endl<<"--------------------------------"<<endl;

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<<endl;

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<<i<<" -eltment masuvy"<<endl;

cin>>mas[i];

}

clrscr();

cout<<"Maemo masuv "<<endl;

Страницы: 1, 2, 3