Quicksort saralash algoritmi

17
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, 
9
3
7
5
2
1
4
4
3
7
5
2
1
9
9
3
7
5
2
1
4
4
3
1
5
2
7
9
4
3
1
2
5
7
9
4
3
1
2
5
7
9
2
3
1
4
2
1
3
4
3
4

18
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 quicksort 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]; 

19
qsort(0,n-1); 
for(i=0; icout << a[i] << " "; 
return 0; } 
Dastur natijasi quyidagicha bo’ladi: 

Download 0,98 Mb.