//Sort_prjamum vuborom

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

{k]=j;

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

if (mas[i]<mas[k]) {k]=i;}

mas[0]=mas[k]; mas[k]=mas[j]; mas[j]=mas[0];

}

cout<<"Masuv vidsortovanuy "<<endl;

vuv(n);

getch();

return 0;

}

Аналіз прямого вибору. Очевидно, що кількість порівнянь ключів Ci на i-ому виборі не залежить від початкового розміщення елементів і дорівнює N-i. Таким чином

Кількість же перестановок залежить від стартової впорядкованості масиву. Це стосується переприсвоєнь у внутрішньому циклі по j при пошуку найменшого ключа. В найкращому випадку початково впорядкованого масиву Mi=4 ; в найгіршому випадку зворотно впорядкованого масиву Mi=Ci+4 ; для довільного масиву рівномовірно можливе значення Mi=Ci/2+4. Тому для оцінки ефективності алгоритму по перестановках можна скористатися наступними співвідношеннями:

;

;

.

Як і в попередньому випадку алгоритм прямого вибору описує процес стійкого сортування.

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

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

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

1) фіксувати, чи були перестановки в процесі деякого етапу. Якщо ні, то - кінець алгоритму ;

2) фіксувати крім факту обміну ще і положення (індекс) останнього обміну. Очевидно, що всі елементи перед ним або після нього відповідно для сортування "бульбашкою" або "камінцем" будуть впорядковані;

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

2.4.1 Метод "бульбашки"

Проведемо більш детальний розгляд методу бульбашки. Нехай маємо масив mas, який необхідно впорядкувати за зростанням.

На першому етапі перевіряємо чи елемент із номером [і-1] не є більший за елемент з номером [i], якщо так, то міняємо місцями. Далі зменшуємо і на 1 з нову проводимо порівняння до тих пір поки і не рівне j (на першому проході = 2). Зробивши перший прохід масиву, ми матимемо на місці 1 елемента найменший. Проходить якби виштовхування найменшого в ліву частину масиву.

Отже, після першого проходу маємо масив, де перший елемент з індексом [1] є вже впорядкований.

Далі аналогічним чином проводимо впорядкування іншої частини масиву, на другому кроці і буде змінюватися від n (n=7 у даному прикладі) до 3.

Запишемо саму програму реалізації даного методу (Файл SORT_4.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_Bulbashka

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

for(i=n;i>=j;i--)

{

if (mas[i-1]>mas[i]){

tmp=mas[i];mas[i]=mas[i-1];mas[i-1]=tmp;

}

cout<<"Masuv vidsortovanuy "<<endl;

vuv(n);

getch();

return 0;}

2.4.2 Метод "камінця"

Даний метод мало чим відрізняється від методу "бульбашки", тому наведемо лише його реалізацію (Файл SORT_5.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_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 (не включаючи його).

Оскільки вказівник на елемент масиву в С++ вважається ітератором довільного доступу, можна впорядкувати частину, або весь масив. Наприклад:

int mas[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. Проте в ній програмісту самому було потрібно написати функцію порівняння елементів для її повноцінної роботи, наприклад:

іnt compare_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);

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

Висновки

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

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

У своїй роботі ми розглянули прямі алгоритми сортування, навели графічне відображення покрокового виконання. Також нами було розроблено ряд програм, для наочної демонстрації роботи кожного окремого методу.

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

Виконуючи дану роботу, ми прийшли до ряду висновків:

- алгоритми прямого сортування, не є складними у розумінні, легко виконувані і прості у реалізації;

- дані алгоритми, що ми розглянули, можна використовувати для сортування даних довільного типу, тобто ці алгоритми в певній мірі є універсальні;

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

- швидкодія прямих методів сортування невелика, але якщо впорядковуваний масив є невеликим або ж сортування проводиться не часто, то ними користуватися є більш вигідно, ніж іншими алгоритмами;

- сортування вставками дає більш відчутну перевагу, якщо вихідний масив близький до впорядкованого стану;

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

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

Оскільки прямі алгоритми сортування вважаються більш простими, дана курсова робота може стати у пригоді при вивченні більш складних алгоритмів сортування, наприклад в графах, списках. Її можна буде використати як початковий матеріал для сортування об'єктів класу за певним ключем. Також у курсовій роботі наведені стандартні процедури сортування з допомогою шаблонів, що теж буде допомогою при подальшому вивченні матеріалу, пов'язаного з сортуванням.

Література

1. Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. - 460 с.

2. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.1. Язык С++. - М.: Бином, 2004. - 544 с.

3. Глушаков С.В. Программирование на Visual C++. - М.: АСТ; Х.: Фоліо, 2003. - 726 с.

4. Дейтел Х. Как программировать на С++. - М.: Бином, 2001. - 1152 с.

5. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. - 709 с.

6. Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. - 668 с.

7. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. - М.:Издательский дом "Вильямс", 2000. - 750 с.

8. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. - 385 с.

9. Культин Н. Б. С/С++ в задачах и примерах. - М., 2002. - 288 с.

10. Кучеренко В. Язык программирования С++ для начинающих и не только. - М.: Майор, 2001. - 160 с.

11. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.

12. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. - 441 с.

13. Мешков А.В. Visual C++ u MFC. - М, 2003. - 1040 с.

14. Павловская Т.А. С/С++: Программирование на языке высокого уровня: Учебник для студ. ВУЗ. М, 2002. - 464 с.

15. Секунов Н.Ю. Самоучитель Visual C++. М., 2002. - 735 с.

16. Франка П. С++: Учебный курс. М., 2002. - 521 с.

17. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. - 240 с.

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