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).
