Samaradorligi bajardi: xolmatov r. T tekshirdi: muxsinov sh. Sh

14
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 
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
1
2
3
4

15
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]; 
qsort(0,n-1); 
for(i=0; icout << a[i] << " "; 
return 0; } 
Dastur natijasi quyidagicha bo’ladi: 

16
Xulosa.
Xulosa qilib shuni aytishim mumkinki, bu mavzuda men massiv elementlarini saralash 
usullarining ichida quicksort ya’ni tez saralash algoritmining qaysidir sohalarda boshqa usullarga 
nisbatan qulaylik tomonlari bilan ajralib turishini ko`rsatishga harakat qildim. Bundan tashqari, 
ya’ni quicksort algoritmidan tashqari saralash algoritmlaridan bubble sort saralash algoritmi, 
insertion sort saralash algoritmlarini tushuntirishga harakat qildim. Ushbu saralash 
algoritmlarining dasturlarini c++ tilida yozganligim uchun bu saralash algoritmlariga yanada 
ko`proq ko`nikma hosil qildim.
Hali sanashni bilmay turib sonlar ustida arifmetik amallar bajarib bo`lmaganidek, men ham 
ushbu kurs ishidagi asosiy qismning birinchi bo`limida massivlar haqida kengroq to`xtalib 
o`tdim. Ikkinchi bo`limda esa saralsh algoritmlarining turlari va ularning bir - biridan farqi haqida 
kengroq tushunchalar keltirib o`tdim. Va nihoyat uchinchi bo`limda kurs ishining asosiy qismini, 
quick sort saralash algoritmi va uning dasturini yozdim. 

17

Download 0,97 Mb.