Курсовая работа: Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів

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(n² ) . Зовнішній цикл виконується (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;