LSD Radix sort

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.

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

String key elementlari bir xil uzunlikda. Amaliyotda ham ko’pincha ID uzunligi bir xil bo’ladi.

Nima uchun key sifatida integer emas, string ishlatilyapti?
Katta web-servislarda milliardlab qatorli ma’lumotlar saqlanadi, ular kelajakda trillion-trilliardga ham yetishi mumkin. Integer tipining limiti trillionlab key saqlashga imkon bermaydi. Shuning uchun string keylardan foydalangan ma’qul. Masalan, Mailchimp servisi obunachi IDsi sifatida obunachining emailini 32 belgili MD5 hash’ga o’girib bazada saqlaydi. Email’lar unikal bo’lishi lozimligi bois, MD5 hash ham unikal key bo’la oladi. Bir xil 32 belgili uzunlikka ega key’larni tartiblashga LSD radix sort’ni qo’llaganda, LSD algoritmining time complexity’si O(N) bo’lgani uchun, boshqa sort algoritmlaridan tezroq ishlaydi.

LSD sort ishlash tartibi

Key uzunligini W deb oladigan bo’lsak, 0 dan W gacha sikl ichida, key’ning ohiridan boshlab boshiga (o’ngdan chapga) har bir belgi bo’yicha tartiblaydi.

Yuqoridagi misolda W uzunligi uchga teng bo’lgani uchun 3ta sikl amal qiladi. Birinchi siklda W-1 belgilar bo’yicha key’larni tartiblaymiz:

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

Ikkinchi siklda, W-2 belgilar bo’yicha tartiblaymiz:

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

Uchinchi siklda W-3 belgilar bo’yicha tartiblaymiz:

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

W sikldan keyin key’lar to’liq tartiblangan holga keladi.

Kod