Kompyuter ilmlari va dasturlashtirish

Radix Sort qanday ishlaydi?
Radix sortning asosiy o'zgaruvchilari quyidagilardir:

• 
  Sana uzunligi
  
• 
  Ma'lumot sonini ifodalovchi radix Algoritmnning asosiy qadamari quyidagicha:
  

1. 
   Ma'lumotlarni tarjima qilish: Ma'lumotlar tarjima qilinishi va ularni saralash uchun foydalanish mumkin bo'lgan formatga o'tkazilishi lozim. Misol uchun, sonlar decimal formatida bo'lsa va 3 raqamli bo'lsa, har bir raqamni o'zi bilan saralash mumkin.
   
2. 
   Radix bo'yicha olish: Ma'lumotlar radix bo'yicha ajratiladi. Bu ya sana uzunligi yoki ma'lumotlarning maxsus bir xususiyati (masalan, sonlar uchun 10) bo'lishi mumkin.
   
3. 
   Hech qanday saralamagan holda elementlarni saralash: Bu qadamda biz ma'lumotlarni bitta tartibda birlashtirishni istamaymiz. Istisno holatlarda, bitta radixdan foydalanish yuqori darajadagi har bir radixdan foydalanish bilan ta'minlanadi.
   
4. 
   Radix bo'yicha saralash: Bu qadamda, ma'lumotlar o'zlarining o'zida saralgan va ularga asoslangan tartibda saraliladi.
   
5. 
   Qiymatlar bo'yicha saralash: Agar ikki yoki undan ko'p element bir xil qiymatga ega bo'lsa, ularni oddiy tarzda saralamaslik mumkin. Shuning uchun, ularni boshqa bir algoritm orqali saralash kerak.
   

Razryadli saralash (Radix sort) ishlash vaqti ,afzalliklari va kamchiliklari?
Kiritilgan butun sonlarda d raqam bo’lsin. Radix Saralash O(d*(n+b)) vaqtni oladi, bunda b raqamlarni ifodalash uchun asos bo'ladi, masalan, o’nlik sistema uchun b 10 ga teng. d ning qiymati nima? _{Agar k maksimal mumkin bo’lgan qiymat bo’lsa, u holda d O (log b} (k)) bo’ladi . Shunday qilib, umumiy vaqt murakkabligi O((n+b) * log _b (k)). Bu katta k uchun taqqoslashga asoslangan tartiblash algoritmlarining vaqt murakkabligidan ko’ra ko’proq ko’rinadi. Avval k ni cheklaylik. k <= n ^c bunda c doimiy bo'lsin. U holda murakkablik O(nLog _b (n)) ga aylanadi. Ammo u hali ham taqqoslashga asoslangan saralash algoritmlaridan ustunkelmaydi.
Agar b qiymatini kattaroq qilsak nima bo'ladi? Vaqt murakkabligini chiziqli qilish uchun b qiymati qanday bo’lishi kerak? Agar b ni n deb belgilasak, vaqt murakkabligini O(n) sifatida olamiz. Boshqacha qilib aytadigan bo’lsak, agar raqamlar n asosda (yoki har bir raqam log ₂ (n) bitni oladi) ifodalangan bo'lsa, biz 1 dan n ^c gacha bo'lgan butun sonlar qatorini saralashimiz mumkin .
Radix Sort barqaror tartibdir, chunki u teng qiymatli elementlarning nisbiy tartibini saqlaydi. Radix tartiblash algoritmi, agar operatsiyalar samarasiz bo’lsa, birlashma tartiblash va Tezkor saralash kabi boshqa tartiblash algoritmlariga qaraganda sekinroq bo'lishi mumkin.
Raqamli tartiblash algoritmi massivdagi barcha massiv elementlari bir xil sonli raqamlarga ega bo’lgan, ko’p sonli raqamlarga ega bo‘lgan bir xil sonli raqamlarga ega bo‘lsa, vaqt murakkabligining eng yomon stsenariysiga duch keladi. Bu shuni anglatadiki, eng katta element n ta raqamga ega deb faraz qilsak, algoritmning ishlash vaqti O(n²) ga teng.