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.
