Qarshi davlat universiteti fizika-matematika fakulteti

3. Quick sort
Quicksort saralash algoritmi bu tezkor saralash degan ma’noni anglatadi. Tezkor saralash ( Quick sort ) algoritmi 1964 - yilda Charlz Hoar tomonidan taklif qilingan. Charliz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “ Tezkor saralash ” algoritmi saralash bo`yicha eng ommabop algoritm.
Bu algoritm ham “ Bo`lib tashla va hukmronlik qil “ ( Bu metod algoritmlarni qurishning asosiy metodlaridan biri. Murakkab masalani yechish uchun uni oddiyroq bo`laklarga ajratish kerak. Massivni ham xuddi shunday saralash mumkin . buning uchun uni ikki bo`lakka ajratamiz, bo`laklarni alohida saralaymiz, saralangan massivlarni birlashtiramiz ) metodiga asoslanadi. Algoritmining g`oyasi: Massivda bo`luvchi element x dan kichik yoki teng bo`lgan elementlar joylashsin, keyin undan katta bo`lgan elementlar joylashsin. Keyin ularni alohida saralaymiz. Agar a massivda n ta element bo`lsa, bo`luvchi element sifatida x=a[n/2] ni olamiz. Chap tomondan x dan kichik katta yoki teng bo`lgan birinchi elementni topamiz, o`ng tomondan esa x dan katta bo`lmagan birinchi elementni topamiz va ikkalasining o`rnini almashtiramiz. Ana shu jarayonni bo`luvchi element x ning chap tomonida undan kichik elementlar, o`ng tomonida esa undan katta bo`lgan elementlar joylashb qolgunicha davom ettiramiz. Shundan so`ng yuqoridagi jarayonni chap tomon uchun alohida o`ng tomon uchun alohida bajaramiz va hakozo. Ko`rinib turganidek bu rekursiya jarayoniga to`g`ri keladi.
Quyida Quick sort saralash algoritmining c++ tilidagi dastur matnini keltiramiz:
#include
using namespace std;
int a[1000];
void qsort(int l, int r)
{ int m, x, j, t, i;
m=(l+r)/2;
x=a[m];
i=l; j=r;
while(i<=j){
while(a[i]while(a[j]>x) j--;
if(i<=j) {
t=a[i]; a[i]=a[j]; a[j]=t;
i++; j--;}
}
if(lif(iint main()
{ int i, n;
cin>>n;
for(i=0; icin>>a[i];
qsort(0,n-1);
for(i=0; icout << a[i] << " ";
return 0; }