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

{

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;

}

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

;

;

;

;

;