MSD Radix sort

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). Keyin rekursiyada key indexed counting ajratgan har bir guruhni alohida-alohida tartiblaymiz. MSD Radix sort algoritmi shu tariqa ishlaydi.

MSD Radix sort ishlash tartibi

Ishlash tartibini misol bilan ko’rib chiqamiz. Bizda quyidagi ro’yhat bor bo’lsin:

0	dab
1	add
2	cab
3	fad
4	fee
5	bad
6	dad
7	bee
8	fed
9	bed
10	ebb
11	ace

Key indexed counting algoritmini qo’llaganimizdan keyin:

0	add
1	ace
2	bad
3	bee
4	bed
5	cab
6	dab
7	dad
8	edd
9	fad
10	fee
11	fed

count[] array’da bosh harflar quyidagicha guruhlangan bo’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 string’larni ham tartiblay oladi.

Kod

MSD Radix sort’ning kamchiliklari

1. Agar kodni debug qilib ko’rgan bo’lsangiz, count[] ga har safar R=128 bo’sh (0) element berilyapti. Demak har safar ortiqcha resurs band qilinyapti. Aslida biz key uchun alphanumeric belgilardan foydalansak, bizga R=62 sig’imli count[] ham kifoya qilardi. Agar faqat kichik (yoki faqat katta) harflardan foydalansak, R=36 bo’lishi yetarli. Shuning uchun, algoritmdan foydalanganda key’dagi belgilarni aniqlab oladigan bo’lsak, bu bizga kodning tezroq ishlashiga yordam beradi.
2. Ikkinchi kamchilik – rekursiya ishlayotganda juda ko’p kichik aux[] array’lar paydo bo’lib, ular alohida-alohida tartiblanyapti. Kichik array’lar uchun insertion sort‘ni qo’llab, kod ishlashini optimallashtirish mumkin.
3. MSD key’lardagi har bir belgini solishtirib chiqqani uchun, bir xil key’larda (duplicate keys) yomon natija ko’rsatadi, chunki bu holda bir xil key’larning har bir belgisini ohirigacha solishtirib chiqadi.

Keyingi mavzuda biz MSD Radix sort’ni Quicksort bilan birga qo’llab uni optimallashtirishga urinamiz.