Dasturchi, frilanser, gik va introvert
Bizga N belgiga ega matndan so’zni qidirib, barcha so’zlarni topish kerak bo’lsin. To’g’ri, so’zni topadigan tayyor sub-string funksiyalar allaqachon mavjud. Ammo texnik intervyu jarayonida qo’yiladigan masalada tayyor funksiyadan foydalanmaslik kerak bo’ladi. Bunda odatiy yechim – brute-force algoritmi yordamida matndagi barcha belgilar solishtirib chiqiladi. Ishlash vaqti – O(N2), tezkor yechim emas.
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.
LSD Radix sort’da string key’larni o’ngdan chapga tartiblab borgan edik. Albatta, chapdan o’ngga ham tartiblab borishning ham imkoni bor. Buning uchun ro’yhatdagi key’larning bosh harfi (belgisi) bo’yicha tartiblaymiz (Key indexed counting).
Biz o’tgan maqolada ko’rib o’tganimiz – key indexed counting tartiblash boshqa algoritmlar uchun asos bo’lib xizmat qiladi. Shu jumladan, LSD (Least Significant Digit) radix sort algoritmi key indexed counting usulini bir xil uzunlikdagi tartiblanadigan string yoki integer qiymatlarning har bir belgisiga qo’llaydi.
Key indeksli sanoq (bundan keyin Key indexed counting, KIC) bizga unikal bo’lmagan key’ga ega ro’yhatlarni tartiblash uchun asqotishi bois, dastlab biz tartiblash algoritmlari haqida eslab olamiz.