Ok, bunisi oson, Quickselect ni o’rganish nimaga kerak deyishingiz mumkin. To’g’ri, shunchaki array’ni o’sish bo’yicha tartiblab, keyin array[k] ni topsa bo’ladi. Quicksort yoki Mergesort yordamida array tartiblangach, k-nchi kichik element topiladi.
Endi savol, nima uchun bizga kerak bo’ladigan k-nchi elementni topish uchun butun array’ni tartiblashimiz kerak? Masalan, 100,000 elementdan iborat array’dan 5-kichik elementni topish uchun ham array’ning hamma sonlarini tartiblashimiz zarurmi? Qanday qilib optimizatsiya qilish mumkin?
Quickselect mana shu optimizatsiyani amalga oshiradi.
Ishlash prinsipi
Quickselectning ishlash prinsipi Quicksort’ga o’xshab ketadi. U ham array’ni pivot bo’yicha ikkiga bo’ladi (partitioning). Farqi – keyin pivot’ni k bilan solishtiradi. Agar pivot > k bo’lsa, pivot’ning chap tarafini qaytadan ikkiga bo’ladi. pivot < k bo’lsa, pivotning o’ng tarafini qaytadan ikkiga bo’ladi. pivot == k bo’lgan holatda array[k] ni qaytaradi.
Mavzu: Partitioning haqida batafsil – Quicksort maqolasida.
Quickselect’da optimizatsiya – array’ning k-nchi elementi bo’lmagan qismlariga tegmaslik hisobiga almashtirishlar sonini keskin kamaytirishga erishiladi. Quickselect qaysidir tomondan binary search‘ning ishlashiga ham o’xshab ketadi.
Kod
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni to’g’ri tartiblash uchun «>» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.
Berilgan funksiyani k-nchi katta elementni topadigan funksiyaga o’zgartirishga urinib ko’ring. 😉
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.