Dasturchi, frilanser, gik va introvert
Dijkstra’ning 3-way partitioning quicksort algoritmi bilan tanishib chiqqan bo’lsangiz kerak. U quicksort’dagi bir xil key’lar uchragan holatida ishlash vaqti ortishini oldini oladi. Biz 3-way quicksort’ga qaytamiz, bu safar bo’luvchi element – pivot’ni key belgilaridan olamiz.
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.
Quicksort bilan tanishib chiqqan bo’lsangiz, algoritmda bo’luvchi element (pivot) array’ni ikkiga bo’ladi. Bunda array[pivot]’ning chap tarafida undan kichkina qiymatlar, o’ng tarafida undan katta qiymatlar o’rin oladi. Ushbu algoritmning kamchiligi shundaki – ro’yhatda bir xil qiymatlar ko’p uchraydigan bo’lsa, ishlash vaqti orta boshlaydi.
Mergesort kabi, Quicksort ham rekursiv algoritm, lekin Quicksort’ning Mergesort’dan farqi – rekursiya ish tugallangach ishga tushadi (Mergesort’da avval rekursiya, keyin ish boshlanardi).