Radix Sort

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.

Radix Sort’ning vaqt murakkabligi

Radix Sort algoritmi manfiy bo‘lmagan butun sonlarni xonama-xona, har safar bitta xona bo‘yicha saralaydi.

Saralanishi kerak bo‘lgan \(n\) ta qiymat bor, \(k\) esa eng katta qiymatdagi xonalar soni.

Radix Sort ishlaganda har bir qiymat radix massiviga ko‘chiriladi, so‘ngra har bir qiymat boshlang‘ich massivga qaytarib ko‘chiriladi. Demak, \(n\) ta qiymat radix massiviga ko‘chiriladi va \(n\) ta qiymat qaytarib ko‘chiriladi. Bu bizga \(n + n=2 \cdot n\) ta amal beradi.

Qiymatlarni yuqorida tasvirlangandek ko‘chirish esa har bir xona uchun bajarilishi kerak. Bu jami \(2 \cdot n \cdot k\) ta amal beradi.

Bu bizga Radix Sort uchun vaqt murakkabligini beradi:

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

Xonalar soni \(k\) qiymatlar soni \(n\) ga nisbatan kichik bo‘lib tursa, Radix Sort, ehtimol, mavjud eng tez saralash algoritmidir.

Xonalar soni \(k\) qiymatlar soni \(n\) bilan bir xil bo‘lgan holatni tasavvur qilishimiz mumkin — bunday holatda vaqt murakkabligi \(O(n \cdot k)=O(n^2)\) bo‘ladi, bu ancha sekin va, masalan, Bubble Sort bilan bir xil vaqt murakkabligiga ega.

Shuningdek, qiymatlar soni \(n\) o‘sishi bilan xonalar soni \(k\) ham o‘sadigan, ya’ni \(k(n)= \log n\) bo‘lgan holatni tasavvur qilishimiz mumkin. Bunday holatda vaqt murakkabligi \(O(n \cdot k)=O(n \cdot \log n )\) bo‘ladi, bu esa, masalan, Quicksort bilan bir xil.

Radix Sort vaqt murakkabligini quyidagi rasmda ko‘ring.

Radix Sort simulyatsiyasi

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.