Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів (стр. 2 из 5)
Зрозуміло, що крім самих методів сортування існує ще більше способів їх реалізації, які в певних випадках прискорюють їх роботу, а в певних випадках їх пригальмовують. Так, для прикладу алгоритм сортування Шела можна реалізувати використовуючи рекурсивні запити, а можна і лінійним програмуванням. Для прикладу, обмін елементів масиву використовуючи операції віднімання та додавання відбувається в загальному швидше ніж введення тимчасової змінної із подальшим її переприсвоєнням.
Розділ ІІ. Прямі методи сортування масивів
2.1Сортування прямим включенням
В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже "готову" послідовність mas[1], mas[2], … ,mas[i] та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1, із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початкова ліва послідовність буде "готовою", оскільки одноелементний масив завжди впорядкований. Продовжуючи по аналогії, в кінці-кінців отримаємо впорядкований список, що містить всі елементи масиву, а новий список відповідно збільшиться. Для реалізації цього алгоритму можна використовувати інший масив, куди будуть добавлятися скопійовані в потрібне місце елементи другого масиву, а можна використовувати той же масив, адже зрозуміло, що один масив росте із тією ж швидкістю що і інший зменшується.
Даний алгоритм можна показати наочно наступним чином:
Розглянемо реалізацію даного алгоритму на нашому масиві. Нехай маємо 7 елементів масиву mas із індексами від 0 до 7. Елемент mas[0] відіграє роль бар’єра, що використовуватиметься нами для обміну елементами і спростить реалізацію алгоритму. Використання додаткового елемента в масиві - "бар’єра" mas[0]=x забезпечує гарантоване припинення процесу просіювання. Це дозволяє зменшити кількість логічних умов в заголовку циклу while до однієї, а кількість логічних операцій від 2i-1 до i на кожному етапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індексу. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об’єму перестановок елементів.
Елемент масиву mas[1], виділений, щоб підкреслити те, що навіть в вихідному стані цю область можна розглядати як невеликий, окремо-впорядкований масив. Фактично, робота алгоритму починається із другого елемента масиву mas[2], до "впорядкованого масиву", в якому тепер будуть знаходитися два елементи.
Таким чином, перші два елементи (2, 8) утворюють невеликий впорядкований список, и нам необхідно додати до нього решту елементів (5, 3, 10, 7, 1). Після добавлення числа 5 отримаємо наступну картинку.
Продовжуючи процес, беремо наступний необроблений елементі вставляємо його в відповідне місце впорядкованого масиву. При цьому з кожнам разом розмір упорядкованої частину збільшується, а інша частина масиву зменшується на ту ж саму величину. В результаті розмір впорядкованого масиву стане рівним розміру початкового масиву, і сортування можна вважати закінченим. На практиці даний процес можна записати так:
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) раз. Тому кількість операцій порівняння буде: