LSD Radix sort'da string key'larni öngdan çapga tartiblab borgan edik. Albatta, çapdan öngga ham tartiblab borişning ham imkoni bor. Buning uçun röyhatdagi key'larning boş harfi (belgisi) böyiça tartiblaymiz (Key indexed counting). Keyin rekursiyada key indexed counting ajratgan har bir guruhni alohida-alohida tartiblaymiz. MSD Radix sort algoritmi şu tariqa işlaydi.

MSD Radix sort işlaş tartibi

Işlaş tartibini misol bilan körib çiqamiz. Bizda quyidagi röyhat bor bölsin:

Key indexed counting algoritmini qöllaganimizdan keyin:

count[] array'da boş harflar quyidagiça guruhlangan böladi:

[ ... 0, // a 2, // b 5, // c 6, // d 8, // e 9, // f 12, // - ... ]

Har bir guruhni alohida-alohida tartiblaymiz. Masalan a guruhida add, ace, b guruhida bad, bee, bed, va hokazo.

MSD Radix sort ning LSD sort'dan ustun tarafi - MSD turli xil uzunlikdagi strinğlarni ham tartiblay oladi.

Kod

MSD Radix sort'ning kamçiliklari

1. Agar kodni debug qilib körgan bölsangiz, count[] ga har safar R=128 böş (0) element berilyapti. Demak har safar ortiqça resurs band qilinyapti. Aslida biz key uçun alphanumeric belgilardan foydalansak, bizga R=62 siğimli count[] ham kifoya qilardi. Agar faqat kiçik (yoki faqat katta) harflardan foydalansak, R=36 bölişi yetarli. Şuning uçun, algoritmdan foydalanganda key'dagi belgilarni aniqlab oladigan bölsak, bu bizga kodning tezroq işlaşiga yordam beradi.
2. Ikkinçi kamçilik - rekursiya işlayotganda juda köp kiçik aux[] array'lar paydo bölib, ular alohida-alohida tartiblanyapti. Kiçik array'lar uçun insertion sort'ni qöllab, kod işlaşini optimallaştiriş mumkin.
3. MSD key'lardagi har bir belgini soliştirib çiqqani uçun, bir xil key'larda (duplicate keys) yomon natija körsatadi, çunki bu holda bir xil key'larning har bir belgisini ohirigaça soliştirib çiqadi.

Keyingi mavzuda biz MSD Radix sort'ni Quicksort bilan birga qöllab uni optimallaştirişga urinamiz.