Тез сұрыптау әдісінің алгоритмін сипаттаңыз

Жылдам сұрыптау (Быстрая сортировка; Quick Sort) — мәліметтерді тез сұрыптауға мүмкіндік беретін алгоритм, атап айтқанда, сандық мәліметтерді өсу реті бойынша немесе мәтіндік мәліметтерді алфавит ретімен орналастыру. Алгоритм тізіммен берілген әрекетті орындайды және тізімнің әр жерінде орналасқан мәліметтерді салыстырады. Бірнеше жүз элементген тұратын айтарлыктай үлкен тізімдер үшін қолданылады.

Ч.Хоар жылдам сұрыптау әдісін ұсынды (QuickSort). Quick Sort алгоритмінің күрделілігі орташалап алғанда 0(n log2n) жақын болады. Сандық мәліметтерді өсу реті бойынша немесе мәтіндік мәліметтерді алфавит ретімен орналастыру алгоритмі. Алгоритм тізіммен берілген әрекетті орындайды және тізімнің әр жерінде орналасқан мәліметтерді салыстырады. Бұл сұрыптауда тиімді нәтижеге қол жеткізу үшін үлкен қашықтыққа орын ауыстыруды орындау қажет. Бірнеше жүз элементтен тұратын айтарлықтай үлкен тізімдер үшін де қолданылады.

Жылдам сұрыптау әдісін зерттеу үшін бөлу процесі қалай жүріп жатқанын қарастыру қажет. Қандай да бір шекаралық х мәнін таңдап, одан кейін массивті тұтасымен қарап шығу керек. Бұдан n салыстыру орындалады.

Берілген шекаралық х мәнінде күтілетін алмастырулар операциясының саны тізбектің бөлінген сол жақтағы элементтер санына тең болады, яғни ықтималдылыққа көбейтілген n-1 алмастыру барысында әрбір осындай элемент өзінің орнына барып түседі. Егер осы элемент осының алдында оң жақта болса, алмастыру орындалады.

Әрбір бөлу процесі массивті екі жартыға бөледі және сұрыптау үшін бар болғаны log n тексеру талап етіледі. Нәтижесінде жалпы салыстырулар саны n*log n, ал жалпы алмастырулар саны -n*logn/6

Бұл әдістің де өзіне тән кемшіліктері бар.

Олардың ішіндегі негізгілерінің бірі n саны аз болған жағдайдайғы өнімділіктің төмендігі.

Ал, бұл әдістің артықшылығына келетін болсақ, шағын бөлікті өңдеу үшін тікелей сұрыптаудың қандай да бір әдісін оңай қосуға болады. Бұл программаның рекурсиялық нұсқасында өте қолайлы.

Жылдам сұрыптау коды мына түрде өрнектеледі:

#include <iostream>

#include <algorithm>

using namespace std;

int first, last,n,i;

void qsort(int *mas, int first, int last)

{

int mid;

int f=first, l=last;

mid=mas[(f+l) / 2];

for (i=0; i<n; i++) cout<<mas[i]<<" "; cout<<endl;

do

{

while (mas[f]<mid) f++;

while (mas[l]>mid) l--;

if (f<=l)

{

swap(mas[l],mas[f]);

f++;

l--;

}

} while (f<l);

if (first<l) qsort(mas, first, l);

if (f<last) qsort(mas, f, last);

}

int main()

{

cin>>n;

int A[99];

for (i=0; i<n; i++)

{

cin>>A[i];

}

first=0; last=n-1;

qsort(A, first, last);

return 0;

}