Mustaqil ish-5 Mavzu: Shablonfunksiyalardafunksiyalarniqaytayuklashmexanizmi

8.2. Tez sara lash ning rekursiv aigoritmi
Rekursiyani amalda q o ‘llash uchun namuna sifatida massiv 
elementlarini tez saralash aigoritmi Quicksort ni ko‘rib chiqamiz. 
Ushbu algoritm massiv elementlarini o ‘sish (yoki kamayish) tartibida 
tartiblash uchun xizmat qiladi.
Faraz qilaylik, massivning 11 elementi quyidagicha joylashgan 
b o ‘lsin (2-rasm).
14
3
2
11 | 5
8
0
2
9
4
20
a[0] 
a[10]
2-rasm . 
Massivning boshlang‘ich holati.
Algoritm g ‘oyasi massivni rekursiv asosda ikkiga ajratish va 
tartiblash amalini ulam ing har biri uchun bajarishni o ‘z ichiga oladi. 
Ajratish chegaraviy deb ataladigan biror elementni tanlash orqali 
amalga oshiriladi. M assiv ikkiga ajratilganidan so‘ng, ular shunday 
qayta ishlanadiki, chegaraviy elementning bir tomonida undan kichik 
yoki teng b o ‘lgan elementlar, ikkinchi tomonida esa katta yoki teng 
b o ‘lgan elementlar joylashadi.
Agar chegaraviy element sifatida 8 ni tanlasak, birinchi tartib­
lashdan keyin m assiv 3-rasmdagi holga keladi. Endi xuddi shu 
jarayonni massivning o ‘ng va chap qismlari uchun qo'llanadi.
112

4 | 3 | 2 | 2 | 5 | 0 | 
|"1T| 
| 11 j 9 |l4 120 
a[0] 
a[10]
3-rasm . 
Massivning dastlabki saralashdan keyingi holati.
Massivni qismlarga ajratish va ularda tartiblash amalini rekursiv 
inexanizm yordamida bajarish mumkin, Buning uchun chegaraviy 
clement indeksi o ‘rtadagi element indeksi shaklida hisoblanadi. Bunda 
“lirst” va “last” lar massiv qismining birinchi va oxirgi element- 
larining indekslarini angalatadi.
M assiv elementlarini rekursiv tartiblash protsedurasini batafsil 
lahlil qilamiz.
M assivning qayta ishlanayotgan qismi chetki elementlari indeks­
larini “left_arrow” hamda “right_arrow” orqali belgilaymiz (4-rasm).