Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів (стр. 4 из 5)
{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;
vuv(n);
//Sort_kamin
for (int j=1;j<n;j++)
for (i=1;i<=(n-j);i++)
{
if (mas[i]>mas[i+1]){
tmp=mas[i];mas[i]=mas[i+1];mas[i+1]=tmp;
}
}
cout<<"Masuv vidsortovanuy "<<endl;
vuv(n);
getch();
return 0;}
2.4.3 Метод шейкерного сортування
Якщо розглянути необхідну кількість дій, що виконується при сортуванні „бульбашковим" методом чи методом „камінця" то вона має порядок O(n2). Зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n на 2 раз. Взагалі, „бульбашкове" сортування відноситься до найменш ефективних методів. Дещо покращати його можна, чергуючи порядок проходу масиву та зупиняючись, коли всі елементи відсортовано. Такий модифікований алгоритм дістав назву „шейкерного" сортування.
Нижче наведемо реалізацію цього методу (Файл SORT_6.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;
vuv(n);
//Sort_Sheikerne
int l,r;
l=2; r=n; k=r;
while (l<r)
{
for(int j=l;j<=r;j++)
if (mas[j]<mas[j-1]) {tmp=mas[j];mas[j]=mas[j-1];mas[j-1]=tmp;k=j;}
r=k-1;
for(j=r;j>=l;j--)
if (mas[j]<mas[j-1]) {tmp=mas[j];mas[j]=mas[j-1];mas[j-1]=tmp;k=j;}
l=k+1;
}
cout<<"Masuv vidsortovanuy "<<endl;
vuv(n);
getch();
return 0;
}
Аналіз алгоритмів на основі прямого обміну. Розглянемо спочатку чисту "бульбашку". Для "камінця" оцінки будуть такими ж самими. Зрозуміло, що кількість порівнянь ключів Ci на i-ому проході не залежить від початкового розміщення елементів і дорівнює N-i. Таким чином
Кількість же перестановок залежить від стартової впорядкованості масиву. В найкращому випадку початково-впорядкованогомасиву Mi=0 ; в найгіршому випадку зворотно-впорядкованогомасиву Mi=Ci*3; для довільного масиву рівноймовірно можливе значення Mi=Ci*3/2. Тому для оцінки ефективності алгоритму по перестановках можна скористатися наступними співвідношеннями:
; 
; 
.Очевидно, що і цей алгоритм, аналогічно з іншими прямими методами, описує процес стійкого сортування.
Розглянемо тепер покращений варіант "шейкерного" сортування. Для цього алгоритму характерна залежність кількості операцій порівняння від початкового розміщення елементів в масиві. В найкращому випадку вже впорядкованої послідовності ця величина буде
. У випадку зворотно-впорядкованогомасиву вона співпадатиме з ефективністю для чистої "бульбашки".Як видно, всі покращення не змінюють кількості переміщень елементів (переприсвоєнь), а лише зменшують кількість повторюваних порівнянь. На жаль операція обміну місцями елементів в пам’яті є "дорожчою" ніж порівняння ключів. Тому очікуваного виграшу буде небагато. Таким чином "шейкерне" сортування вигідне у випадках, коли відомо, що елементи майже впорядковані. А це буває досить рідко.
2.5 Порівняння прямих методів сортування масивів
З метою порівняння методів сортування масивів було виконано тестування. Для кожного методу за алгоритмом було написано підпрограму на С++, після чого виконано тестування для масивів цілих чисел розміром 1024, 4096 та 16384. Результати тестування (кількість секунд з точністю до сотих) на комп’ютері Pentium-II/450 наведено у таблиці. Для кожного розміру масиву використовувалось 3 способи його побудови:
1) вже впорядкований за зростанням масив;
2) масив, впорядкований за спаданням;
3) масив з випадкових чисел.
24 4096 16384
Прямим включ. .00 0.05 0.00 .00 0.88 0.44 .00 14.01 6.98
Бінарним включ..00 0.06 0.06 .00 0.61 0.28 .05 9.67 4.83
Прямим вибором.06 0.05 0.00 .50 0.49 0.49 .30 8.46 8.29
Бульбашка/Камінець .00 0.11 0.11 .54 1.70 1.21 .73 27.79 19.45
Шейкерне .00 0.11 0.05 .00 1.71 0.99 .00 27.30 15.82
Результати показують, що оскільки швидкість сортування елементів є квадратичною, то час виконання практично однаковий, в той же час, для вже відсортованого масиву хороші результати продемонстрували сортування включенням та шейкерне сортування, у яких кількість операцій суттєво залежить від вигляду масиву. Отже, ці прості алгоритми сортування можна використовувати для „майже" відсортованих масивів, тобто, коли до відсортованого масиву додають m елементів (m<<n).
Розділ ІІІ. Огляд функцій сортування із стандартної бібліотеки С++
Мова програмування С++ має в своєму складі функції, які дають змогу виконувати сортування елементів довільного типу без реалізації алгоритмів. Так, функція sort має декілька версій, в базовому її варіанті прототип виглядає наступним чином:
Void sort(Iterarot begin, Iterator end);
В якості параметрів функції використовуються два ітератори довільного доступу, призначені для роботи з окремим контейнером класу. З допомогою функціїsort дані контейнера впорядковуються, починаючи з елемента begin і закінчуючи елементом end (не включаючи його).
Оскільки вказівник на елемент масиву в С++ вважається ітератором довільного доступу, можна впорядкувати частину, або весь масив. Наприклад:
intmas[7]= {0, 10, 2, 0, 4, 15, 6}
//Елементи масиву будуть впорядковані. Зверніть увагу на те,
// що ім’яmas використовується в якості вказівника на перший
// елемент,mas+7, вказує на елемент, що знаходиться
// на одну позицію дальше границі масиву
sort(mas, mas+7);
Проте, дана функція підтримується лише новими компіляторами (Файл SORT_7.CPP).
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <algorithm.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;
vuv(n);
//Sort_Bibliotrchna_fukccia
sort(mas, mas+n);
cout<<"Masuv vidsortovanuy "<<endl;
vuv(n);
getch();
return 0;
}
Крім даної функції, в С++ існує ще ряд інших призначених для сортування масивів довільних типів. Наприклад, однією із перших функцій даного напрямку, що ввійшла в стандартну бібліотеку мови С була функція qsort. Проте в ній програмісту самому було потрібно написати функцію порівняння елементів для її повноцінної роботи, наприклад:
іntcompare_integers(const void* p1, const void* p2)
{
returne* ((int *)) p1)-*((int*)p2));
}
А вже маючи готову функцію порівняння, можна використовувати функцію qsort. Наприклад, для сортування масиву цілих чисел виклик функції буде мати вигляд:
int mas[7]= {0, 10, 2, 0, 4, 15, 6};
qsort((void*)mas,7,sizeof(int),compare_integer);
Використовуючи дані функції, можна зробити порівняльний аналіз затрат для програмування власних, швидкості виконання, затрачених ресурсів.
Висновки
Виконуючи курсову роботу, ми опрацювали тематичну літературу, провели історичний огляд понять алгоритмів, їх застосування. Провели аналіз методів сортування та застосування їх у повсякденному житті.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
У своїй роботі ми розглянули прямі алгоритми сортування, навели графічне відображення покрокового виконання. Також нами було розроблено ряд програм, для наочної демонстрації роботи кожного окремого методу.
Нами було проведений детальний аналіз швидкодії кожного алгоритму, проведено порівняльний аналіз між швидкодією прямих методів сортування.
Виконуючи дану роботу, ми прийшли до ряду висновків:
- алгоритми прямого сортування, не є складними у розумінні, легко виконувані і прості у реалізації;
- дані алгоритми, що ми розглянули, можна використовувати для сортування даних довільного типу, тобто ці алгоритми в певній мірі є універсальні;
- сортування методами вибору і сортування вставками як при найгіршому, так і при середньому варіанті мають квадратичний час виконання.
- швидкодія прямих методів сортування невелика, але якщо впорядковуваний масив є невеликим або ж сортування проводиться не часто, то ними користуватися є більш вигідно, ніж іншими алгоритмами;