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:

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

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:

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

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

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

Uchinchi siklda W-3 belgilar bo’yicha tartiblaymiz:

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

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

Kod