4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Birlashtirib saralash (Merge sort)

3. Birlashtirish bosqichi qanday amalga oshiriladi? 
5-§. Tez saralash algoritmi 
Tezkor saralash (Quick Sort). Saralashning eng yaxshi 
algoritmlari oʻnligi tuzilganda, koʻplab dasturchilar roʻyxati orasida 
Tezkor saralash (Quick Sort) algoritmini koʻrishimiz mumkin. Oʻtgan 
mavzuda saralash algoritmlarining eng yaxshilaridan biri sifatida 
birlashtirib saralash (Merge Sort) algoritmni koʻrib chiqqandik. Shuning 
uchun Quick Sort algoritmining qanday afzalliklari mavjud, degan tabiiy 
savol paydo boʻladi?  
Amaliy nuqtai nazardan Quicksort algoritmi raqobatbardosh 
boʻlib, koʻpincha MergeSort algoritmidan ustun turadi va shu sababli bu 
koʻplab dasturlash kutubxonalarida standart tartiblash usuli hisoblanadi.
Quicksort algoritmining MergeSort algoritmidan katta ustunligi 
shundaki, u bir joyda ishlaydi - u kirish massivi bilan faqat 
elementlarning juft toʻgʻridan-toʻgʻri almashinuvini takrorlash orqali 
ishlaydi va shu sababli oraliq uchun faqat ozgina qoʻshimcha tezkor 
xotira kerak boʻladi. 
Tezkor saralash (Quick sort – Xoara metodi) koʻpincha qsort deb 
nomlanadi (uning nomi C standart kutubxonasida) - bu ingliz kompyuter 
olimi Toni Xoara tomonidan 1960-yilda Moskva davlat universitetida 
ishlab yurgan paytlarida yaratilgan saralash algoritmi hisoblanadi. 
Massivlarni saralash boʻyicha eng tez ma‘lum boʻlgan universal 
algoritmlardan biri: n elementni saralashda oʻrtacha O (nlogn) 
almashinuv boʻladi. Bir qator kamchiliklar mavjudligi sababli amalda 
odatda ba‘zi bir oʻzgartirishlar bilan qoʻllaniladi. 
Umumiy tavsif. QuickSort - bu toʻgʻridan-toʻgʻri almashinuvni 
saralash algoritmining (Bubble Sort va Shaker Sort algoritmlari) sezilarli 
darajada takomillashtirilgan variant boʻlib, u past samaradorligi bilan 
ham tanilgan. Asosiy farq shundaki, birinchi navbatda, almashtirishlar 
mumkin boʻlgan masofada amalga oshiriladi va har bir oʻtishdan keyin 
elementlar ikkita mustaqil guruhga boʻlinadi. (Shunday qilib, eng 
samarasiz toʻgʻridan-toʻgʻri saralash usulini takomillashtirish eng 
samarali takomillashtirilgan usullardan birini beradi.) 

---

71 
Algoritmning umumiy gʻoyasi quyidagicha: 
1) Massivdan ―tayanch‖ elementni tanlang. Bu massivdagi har 
qanday element boʻlishi mumkin. Algoritmning toʻgʻriligi 
―tayanch‖ elementini tanlashga bogʻliq emas, lekin ba‘zi 
hollarda uning samaradorligi kuchli bogʻliq boʻlishi mumkin 
(pastga qarang). 
2) Qolgan barcha elementlarni ―tayanch‖ elementi bilan taqqoslang 
va ularni massiv ichida tartiblang, shunday qilib massivni 
ketma-ket 
uchta 
doimiy 
segmentga 
boʻling: 
"tayanch 
elementdan kichikroq elementlar, "tayanch elementga teng 
elementlar" va "tayanch elementdan katta elementlar". 
3) "Kichik" va "katta" qiymatlar segmentlari uchun segmentning 
uzunligi birdan katta boʻlsa, bir xil amallar ketma-ketligini 
bajaring. 
Amalda massiv odatda uchga emas, balki ikki qismga boʻlinadi: 
masalan, "tayanch elementdan kichikroq" va "tayanch elementga teng va 
katta". Bu yondashuv odatda yanada samaraliroq boʻladi, chunki bu 
qismlarni ajratish algoritmini soddalashtiradi (pastga qarang). 
Xoara bu usulni mashinada tarjima qilish uchun ishlab chiqdi; 
lugʻat magnit lentada saqlangan va qayta ishlangan matn soʻzlarini 
saralash, ularni tarjima qilmasdan, lentaning bir qatorida olish 
imkoniyatini yaratdi. 
Algoritmni Xoara Sovet Ittifoqida boʻlganida ixtiro qilgan, u yerda 
u Moskva universitetida kompyuter tarjimasini oʻrgangan va ruscha-
inglizcha soʻzlashuv kitobini ishlab chiqishda ishlagan.