DSA Radix Sort (razryad bo‘yicha saralash)

Radix Sort

Radix Sort algoritmi massivni eng kichik razryaddagi raqamdan (eng o‘ngdagi raqamdan) boshlab, alohida raqamlar bo‘yicha saralaydi.

Radiks (yoki asos) — sanoq sistemasidagi turli raqamlar soni. Biz odatda foydalanadigan o‘nlik sanoq sistemasida 0 dan 9 gacha bo‘lgan 10 ta turli raqam mavjud.

Radix Sort radiksdan shunday foydalanadiki, o‘nlik qiymatlar e’tibordagi raqamga mos ravishda 10 ta turli chelakka (yoki konteynerga) joylashtiriladi, so‘ngra keyingi raqamga o‘tishdan oldin yana massivga qaytariladi.

Radix Sort — faqat manfiy bo‘lmagan butun sonlar bilan ishlaydigan, taqqoslashga asoslanmagan algoritm.

Radix Sort algoritmini quyidagicha tavsiflash mumkin:

Barqaror saralash

Natija to‘g‘ri saralangan bo‘lishi uchun Radix Sort elementlarni barqaror tarzda saralashi kerak.

Barqaror saralash algoritmi — bir xil qiymatli elementlarning saralashdan oldingi va keyingi tartibini saqlab qoladigan algoritm. Aytaylik, bizda "K" va "L" degan ikkita element bor, bunda "K" "L" dan oldin keladi va ikkalasining qiymati ham "3" ga teng. Agar massiv saralangandan keyin ham "K" elementi "L" dan oldin kelsa, saralash algoritmi barqaror hisoblanadi.

Avval alohida ko‘rib chiqqan algoritmlarimiz uchun barqaror saralash haqida gapirishning unchalik ma’nosi yo‘q, chunki ular barqaror bo‘ladimi yoki yo‘qmi, natija bir xil bo‘lardi. Ammo Radix Sort uchun saralash barqaror tarzda bajarilishi muhim, chunki elementlar har safar faqat bitta raqam bo‘yicha saralanadi.

Shunday qilib, elementlarni eng kichik razryaddagi raqam bo‘yicha saralab, keyingi raqamga o‘tgandan keyin oldingi razryad bo‘yicha allaqachon bajarilgan saralash ishini buzmaslik muhim, shuning uchun Radix Sort har bir razryad bo‘yicha saralashni barqaror tarzda bajarishiga e’tibor berishimiz kerak.

Quyidagi simulyatsiyada chelaklarga ajratish orqali saralash ichkarida qanday bajarilishi ko‘rsatilgan. Barqaror saralash qanday ishlashini yaxshiroq tushunish uchun beqaror tarzda saralashni ham tanlashingiz mumkin, bu esa noto‘g‘ri natijaga olib keladi. Saralash shunchaki elementlarni chelaklarga massiv boshidan emas, balki oxiridan boshlab joylashtirish orqali beqaror qilinadi.

Qo‘lda bajarib ko‘rish

Radix Sort’ni dasturlash tilida amalda amalga oshirishdan oldin, u qanday ishlashini yanada yaxshiroq tushunib olish uchun saralashni qo‘lda bajarib ko‘raylik.

1-qadam: Saralanmagan massiv va qiymatlarni ularga mos 0 dan 9 gacha bo‘lgan radikslar bo‘yicha joylashtirish uchun bo‘sh massivdan boshlaymiz.

2-qadam: Eng kichik razryaddagi raqamga e’tibor qaratib, saralashni boshlaymiz.

3-qadam: Endi elementlarni e’tibordagi raqamga qarab radiks massividagi to‘g‘ri pozitsiyalarga o‘tkazamiz. Elementlar myArray boshidan olinadi va radixArray’dagi to‘g‘ri pozitsiyaga qo‘shiladi.

4-qadam: Elementlarni dastlabki massivga qaytaramiz, endi eng kichik razryaddagi raqam bo‘yicha saralash bajarildi. Elementlar radixArray oxiridan olinadi va myArray boshiga qo‘yiladi.

5-qadam: E’tiborni keyingi raqamga qaratamiz. E’tibor bering, 45 va 25 qiymatlari bir-biriga nisbatan hanuz boshidagi tartibda turibdi, chunki biz barqaror tarzda saralaymiz.

6-qadam: Elementlarni e’tibordagi raqamga qarab radiks massiviga o‘tkazamiz.

7-qadam: Elementlarni radixArray oxiridan myArray boshiga qaytaramiz.

Saralash yakunlandi!

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Ko‘rib turibmizki, qiymatlar massivdan olinib, joriy e’tibordagi radiksga qarab radiks massiviga joylashtiriladi. So‘ngra qiymatlar biz saralamoqchi bo‘lgan massivga qaytariladi.

Qiymatlarni saralamoqchi bo‘lgan massivdan olib, yana unga qaytarish qiymatdagi raqamlarning maksimal soni qancha bo‘lsa, shuncha marta bajarilishi kerak. Masalan, agar saralanishi kerak bo‘lgan massivdagi eng katta son 437 bo‘lsa, har bir raqam uchun bir martadan, jami uch marta saralashimiz kerakligini bilamiz.

Shuningdek, muayyan radiksda, ya’ni indeksda bittadan ortiq qiymat saqlanishi uchun radiks massivi ikki o‘lchamli bo‘lishi kerakligini ko‘ramiz.

Avval aytib o‘tilganidek, saralash barqaror bo‘lishi uchun qiymatlarni ikki massiv o‘rtasida e’tibordagi radiksi bir xil bo‘lgan qiymatlarning tartibini saqlaydigan tarzda ko‘chirishimiz kerak.

Radix Sort’ni amalga oshirish

Radix Sort algoritmini amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanishi kerak bo‘lgan, manfiy bo‘lmagan butun sonlardan iborat massiv.
2. Qiymatlarni joriy e’tibordagi radiksga qarab saqlash uchun 0 dan 9 gacha indeksli ikki o‘lchamli massiv.
3. Saralanmagan massivdan qiymatlarni olib, ularni ikki o‘lchamli radiks massividagi to‘g‘ri pozitsiyaga joylashtiradigan sikl.
4. Qiymatlarni radiks massividan dastlabki massivga qaytaradigan sikl.
5. Eng katta qiymatda nechta raqam bo‘lsa, shuncha marta bajariladigan tashqi sikl.

Natijaviy kod quyidagicha ko‘rinadi:

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(myArray)
exp = 1

while maxVal // exp > 0:

    while len(myArray) > 0:
        val = myArray.pop()
        radixIndex = (val // exp) % 10
        radixArray[radixIndex].append(val)

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()
            myArray.append(val)

    exp *= 10

print("Sorted array:", myArray)

7-qatorda butun bo‘lishdan ("//") foydalanamiz: while sikli birinchi marta bajarilganda maksimal qiymat 802 ni 1 ga, keyingi safar 10 ga, oxirgi safar esa 100 ga bo‘lamiz. "//" butun bo‘lishdan foydalanilganda kasr qismidagi raqamlar tashlab yuboriladi va butun son qaytariladi.

11-qatorda qiymatni radixArray’ning qayeriga qo‘yish uning radiksi, ya’ni e’tibordagi raqami asosida hal qilinadi. Masalan, tashqi while sikli ikkinchi marta bajarilganda exp 10 ga teng bo‘ladi. 170 qiymatini 10 ga bo‘lsak, 17 hosil bo‘ladi. "%10" amali 10 ga bo‘lib, qoldiqni qaytaradi. Bu holda 17 bir marta 10 ga bo‘linadi va 7 qoldiq qoladi. Shunday qilib, 170 qiymati radixArray’ning 7 indeksiga joylashtiriladi.

Boshqa saralash algoritmlaridan foydalanadigan Radix Sort

Aslida Radix Sort’ni istalgan boshqa saralash algoritmi bilan birga amalga oshirish mumkin, faqat u barqaror bo‘lishi kerak. Bu shuni anglatadiki, muayyan raqam bo‘yicha saralashga kelganda counting sort yoki bubble sort kabi istalgan barqaror saralash algoritmi ish beradi.

Quyida alohida raqamlar bo‘yicha saralash uchun Bubble Sort’dan foydalanadigan Radix Sort’ning amalga oshirilishi keltirilgan:

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
def radixSortWithBubbleSort(arr):
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        radixArray = [[],[],[],[],[],[],[],[],[],[]]
        
        for num in arr:
            radixIndex = (num // exp) % 10
            radixArray[radixIndex].append(num)
        
        for bucket in radixArray:
            bubbleSort(bucket)
        
        i = 0
        for bucket in radixArray:
            for num in bucket:
                arr[i] = num
                i += 1
        
        exp *= 10

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixSortWithBubbleSort(myArray)
print("Sorted array:", myArray)

Radix Sort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Radix Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Radix Sort’ning vaqt murakkabligi:

\[ \underline{\underline{O(n \cdot k)}} \]

Bu Radix Sort saralanishi kerak bo‘lgan qiymatlar \(n\) ga ham, eng katta qiymatdagi raqamlar soni \(k\) ga ham bog‘liqligini anglatadi.

Radix Sort uchun eng yaxshi holat — saralanadigan qiymatlar ko‘p, ammo qiymatlardagi raqamlar kam bo‘lgan holat. Masalan, saralanadigan qiymatlar milliondan ortiq bo‘lib, eng katta qiymat atigi uch xonali 999 soni bo‘lsa. Bunday holatda vaqt murakkabligi \(O(n \cdot k)\) ni shunchaki \(O(n)\) gacha soddalashtirish mumkin.

Radix Sort uchun eng yomon holat — eng katta qiymatdagi raqamlar soni saralanadigan qiymatlar soniga teng bo‘lgan holat. Bu, ehtimol, ko‘p uchraydigan holat emas, ammo bu holda vaqt murakkabligi \(O(n^2)\) bo‘lardi.

Eng o‘rtacha yoki keng tarqalgan holat, ehtimol, raqamlar soni \(k\) taxminan \(k(n)= \log n\) bo‘lgan holatdir. Shunday bo‘lsa, Radix Sort’ning vaqt murakkabligi \(O(n \cdot \log n )\) bo‘ladi. Bunday holatga misol sifatida saralanadigan qiymatlar 1000000 ta bo‘lib, qiymatlar 6 xonali bo‘lgan holatni keltirish mumkin.

Radix Sort uchun mumkin bo‘lgan turli vaqt murakkabliklarini quyidagi rasmda ko‘ring.

Amallar soni eng yomon holat \(O(n^2)\) (qizil chiziq) va eng yaxshi holat \(O(n)\) (yashil chiziq) oralig‘iga qanday tushishini ko‘rish uchun Radix Sort’ning turli simulyatsiyalarini ishga tushiring.

Turli qiymatlarni ifodalovchi ustunlar yaxshi ko‘rinishi uchun oynaga sig‘adigan qilib masshtablangan. Shu sababli 7 xonali qiymatlar 2 xonali qiymatlardan atigi 5 marta kattadek ko‘rinadi, ammo aslida 7 xonali qiymatlar 2 xonali qiymatlardan 5000 marta katta!

Agar \(n\) va \(k\) ni o‘zgarmas qoldirsak, yuqoridagi simulyatsiyadagi "Tasodifiy", "Kamayish tartibida" va "O‘sish tartibida" variantlari bir xil miqdordagi amallarga olib keladi. Buning sababi, uchala holatda ham bir xil jarayon sodir bo‘ladi.

Radix Sort must use a  
sorting algorithm.