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