Razryadli saralash (radix sort)
Radix Saralash
Radix Sort algoritmi massivni eng kichik muhim raqamdan (eng o‘ngdagi) boshlab, alohida raqamlar bo‘yicha tartiblaydi.
Radix Sort qilish uchun tugmani bosing, bir vaqtning o‘zida bir qadam (raqam).
{{ msgDone }}Radiks (yoki asos) - bu sanoq sistemasidagi yagona raqamlar soni. Biz odatda foydalanadigan o‘nlik sanoq tizimida 0 dan 9 gacha bo‘lgan 10 xil raqam mavjud.
Radix Sort radixdan foydalanadi, shunda kasr qiymatlari fokusdagi raqamga mos keladigan 10 xil chelaklarga (yoki konteynerlarga) joylashtiriladi va keyingi raqamga o‘tishdan oldin yana massivga kiritiladi.
Radix Sort bu qiyosiy bo‘lmagan algoritm bo‘lib, u faqat manfiy bo‘lmagan butun sonlar bilan ishlaydi.
Radix Sort algoritmini quyidagicha tasvirlash mumkin:
Qanday ishlaydi:
- Eng kam ahamiyatli raqamdan boshlang (eng o‘ng raqam).
- Fokusdagi raqam asosida qiymatlarni saralab, avval qiymatlarni fokusdagi raqam asosida to‘g‘ri chelakka qo‘ying va keyin ularni to‘g‘ri tartibda massivga qo‘ying.
- Keyingi raqamga o‘ting va yuqoridagi bosqichda bo‘lgani kabi, hech qanday raqam qolmaguncha qayta tartiblang.
Barqaror saralash
Natija to‘g‘ri tartiblangan bo‘lishi uchun Radix Sort elementlarni barqaror tarzda tartiblashi kerak.
Barqaror saralash algoritmi tartiblashdan oldin va keyin bir xil qiymatdagi elementlar tartibini saqlaydigan algoritmdir. Aytaylik, bizda ikkita "K" va "L" elementi bor, bu yerda "K" "L" dan oldin keladi va ularning ikkalasi ham "3" qiymatiga ega. Agar massiv tartiblangandan keyin ham “K” elementi “L” dan oldin kelsa, tartiblash algoritmi barqaror hisoblanadi.
Biz alohida ko‘rib chiqqan oldingi algoritmlar uchun barqaror saralash algoritmlari haqida gapirishning ma’nosi yo‘q, chunki ular barqaror yoki barqaror bo‘lmasa, natija bir xil bo‘ladi. Ammo Radix Sort uchun saralash barqaror tarzda amalga oshirilishi muhim, chunki elementlar bir vaqtning o‘zida faqat bitta raqam bo‘yicha tartiblanadi.
Shunday qilib, elementlarni eng muhim raqam bo‘yicha saralab, keyingi raqamga o‘tgandan so‘ng, oldingi raqam pozitsiyasida allaqachon bajarilgan saralash ishlarini yo‘q qilmaslik kerak va shuning uchun biz Radix Sort har bir raqam pozitsiyasi bo‘yicha tartiblashni barqaror tarzda bajarishiga e’tibor berishimiz kerak.
Quyidagi simulyatsiyada chelaklarga asosiy saralash qanday amalga oshirilganligi ko‘rsatilgan. Barqaror saralash qanday ishlashini yaxshiroq tushunish uchun siz beqaror tarzda saralashni ham tanlashingiz mumkin, bu noto‘g‘ri natijaga olib keladi. Saralash elementlarni chelaklarga massiv boshidan emas, balki massiv oxiridan joylashtirish orqali beqaror holga keltiriladi.
Stable sort?
{{ msgDone }}Qo‘lda yugurish
Keling, Radix Sort dasturini dasturlash tilida amalga oshirishdan oldin qanday ishlashini yaxshiroq tushunish uchun tartiblashni qo‘lda qilishga harakat qilaylik.
1-qadam: Biz tartiblanmagan massivdan va 0 dan 9 gacha bo‘lgan mos radikallar bilan qiymatlarni moslashtirish uchun bo‘sh massivdan boshlaymiz.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
2-qadam: Biz eng kam ahamiyatli raqamga e’tibor qaratish orqali tartiblashni boshlaymiz.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
3-qadam: Endi biz elementlarni fokusdagi raqamga muvofiq radix massividagi to‘g‘ri joylarga o‘tkazamiz. Elementlar myArray boshidan olinadi va radixArraydagi to‘g‘ri joyga suriladi.
myArray = [ ]
radixArray = [ [40], [], [], [33], [24], [45, 25], [], [17], [], [] ]
4-qadam: Biz elementlarni dastlabki massivga qaytaramiz va saralash endi eng kam ahamiyatli raqam uchun amalga oshiriladi. Elementlar radixArray oxiridan olinadi va myArray boshiga qo‘yiladi.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
5-qadam: Biz diqqatni keyingi raqamga o‘tkazamiz. E’tibor bering, 45 va 25 qiymatlari avvalgidek bir-biriga nisbatan bir xil tartibda, chunki biz barqaror tarzda saralaymiz.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
6-qadam: Biz elementlarni radix massiviga fokuslangan raqamga muvofiq o‘tkazamiz.
myArray = [ ]
radixArray = [ [], [17], [24, 25], [33], [40, 45], [], [], [], [], [] ]
7-qadam: Biz elementlarni radixArray orqasidan myArray boshiga qaytaramiz.
myArray = [ 17, 24, 25, 33, 40, 45 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Saralash tugadi!
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
radixArray = [ [
Python-da Radix Sort-ni qo‘llang
Radix Sort algoritmini amalga oshirish uchun bizga kerak:
- Saralash kerak bo‘lgan manfiy bo‘lmagan butun sonli massiv.
- Fokusda joriy radix bilan qiymatlarni saqlash uchun indeksi 0 dan 9 gacha bo‘lgan ikki o‘lchovli massiv.
- Saralanmagan massivdan qiymatlarni oladigan va ularni ikki o‘lchovli radiks massivida to‘g‘ri joyga qo‘yadigan sikl.
- Radix massividan qiymatlarni dastlabki massivga qaytaradigan sikl.
- Eng yuqori qiymatdagi raqamlar qancha bo‘lsa, shuncha marta ishlaydigan tashqi sikl.
Olingan kod quyidagicha ko‘rinadi:
Misol
Python dasturida Radix Sort algoritmidan foydalanish:
mylist = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", mylist)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(mylist)
exp = 1
while maxVal // exp > 0:
while len(mylist) > 0:
val = mylist.pop()
radixIndex = (val // exp) % 10
radixArray[radixIndex].append(val)
for bucket in radixArray:
while len(bucket) > 0:
val = bucket.pop()
mylist.append(val)
exp *= 10
print(mylist)
Misolni ishga tushirish »
7-qatorda biz maksimal qiymatni 802 ga birinchi marta while sikli ishlaganda, keyingi safar 10 ga va oxirgi marta 100 ga bo‘lish uchun qavat bo‘linmasidan ("//") foydalanamiz. "//" qavat bo‘linmasidan foydalanilganda, kasrdan tashqari har qanday raqam e’tiborga olinmaydi va butun son qaytariladi.
11-qatorda radixArray-da uning radixiga yoki fokusdagi raqamga qarab qiymatni qaerga qo‘yish qaror qilinadi. Misol uchun, tashqi while siklining ikkinchi marta ekspluatatsiyasi 10 bo‘ladi. 170 ni 10 ga bo‘lish qiymati 17 bo‘ladi. "%10" operatsiyasi 10 ga bo‘linadi va qolganini qaytaradi. Bu holda 17 bir marta 10 ga bo‘linadi va 7 qoladi. Shunday qilib, 170 qiymati radixArray-dagi 7-indeksga joylashtiriladi.
Boshqa saralash algoritmlaridan foydalangan holda Radix Sort
Radix Sort, agar u barqaror bo‘lsa, boshqa har qanday tartiblash algoritmi bilan birgalikda amalga oshirilishi mumkin. Bu shuni anglatadiki, ma’lum bir raqam bo‘yicha saralash haqida gap ketganda, har qanday barqaror tartiblash algoritmi ishlaydi, masalan, hisoblash saralash yoki qabariq tartiblash.
Bu alohida raqamlar bo‘yicha tartiblash uchun Bubble Sort-dan foydalanadigan Radix Sort ilovasi:
Misol
Bubble Sortdan foydalanadigan Radix Sort algoritmi:
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:
radixList = [[],[],[],[],[],[],[],[],[],[]]
for num in arr:
radixIndex = (num // exp) % 10
radixList[radixIndex].append(num)
for bucket in radixList:
bubbleSort(bucket)
i = 0
for bucket in radixList:
for num in bucket:
arr[i] = num
i += 1
exp *= 10
mylist = [170, 45, 75, 90, 802, 24, 2, 66]
radixSortWithBubbleSort(mylist)
print(mylist)
Misolni ishga tushirish »
Radix saralash vaqtining murakkabligi
Radix Sort uchun vaqt murakkabligi: \( O(n \cdot k) \)
Bu shuni anglatadiki, Radix Sort ham tartiblanishi kerak bo‘lgan qiymatlarga ham bog‘liq \(n\) va eng yuqori qiymatdagi raqamlar soni \(k\).
Radix Sort uchun eng yaxshi holat stsenariysi saralanadigan qiymatlar ko‘p bo‘lsa, lekin qiymatlar bir nechta raqamga ega bo‘lsa. Misol uchun, saralash uchun milliondan ortiq qiymatlar mavjud bo‘lsa va eng yuqori qiymat 999 bo‘lsa, faqat uchta raqam bilan. Bunday holda vaqt murakkabligi \(O(n \cdot k)\) shunchaki \(O(n)\) ga soddalashtirilishi mumkin.
Radix Sort uchun eng yomon holat stsenariysi, eng yuqori qiymatda tartiblash uchun qiymatlar qancha raqamlar bo‘lsa, bo‘ladi. Bu, ehtimol, umumiy stsenariy emas, lekin bu holda vaqt murakkabligi \(O(n^2)\) bo‘ladi.
Eng o‘rtacha yoki keng tarqalgan holat, agar \(k\) raqamlar soni \(k(n)= \log n\) kabi bo‘lsa. Agar shunday bo‘lsa, Radix Sort vaqt murakkabligini oladi \(O(n \cdot \log n )\). Saralash uchun 1000000 ta qiymat bo‘lsa va qiymatlar 6 ta raqamga ega bo‘lsa, bunday holatga misol bo‘ladi.
Quyidagi rasmda Radix Sort uchun turli vaqt murakkabliklarini ko‘ring.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!