مرتب‌سازی رقمی

مرتب‌سازی رقمی (Radix Sort) نوعی الگوریتم مرتب‌سازی غیرمقایسه‌ای است که با استفاده از ویژگی ارقام آن‌ها را مرتب می‌کند و به طور معمول دارای مرتبه‌ی زمانی $\mathcal{O}(d \cdot (n + k))$ است که $d$ تعداد ارقام بیشینه و $k$ دامنه‌ی مقادیر ممکن هر رقم است. این الگوریتم غالباً پایدار بوده و برای مرتب کردن اعداد صحیح یا رشته‌ها کاربرد دارد.

ایده‌ی الگوریتم این است که مرتب‌سازی را به صورت رقم به رقم از کم‌ارزش‌ترین رقم تا پرارزش‌ترین رقم انجام دهیم. مرتب‌سازی هر رقم معمولاً توسط مرتب‌سازی پایدار دیگری مثل مرتب‌سازی شمارشی (Counting Sort) انجام می‌شود.

الگوریتم کلی در چند مرحله به صورت زیر است:

۱. تعیین بیشینه‌ی طول ارقام بزرگ‌ترین عدد موجود در آرایه.

۲. از کم‌ارزش‌ترین رقم شروع می‌کنیم (یکان، دهگان و …).

۳. در هر مرحله بر اساس رقم فعلی آرایه را مرتب می‌کنیم (مثلاً با مرتب‌سازی شمارشی).

۴. به رقم بعدی رفته و مرتب‌سازی را تکرار می‌کنیم تا تمام ارقام پردازش شوند.

مثلاً برای آرایه‌ی $170, 45, 75, 90, 802, 24, 2, 66$ مرتب‌سازی رقمی به صورت زیر عمل می‌کند: $$170, 90, 802, 2, 24, 45, 75, 66$$ $$802, 2, 24, 45, 66, 170, 75, 90$$ $$2, 24, 45, 66, 75, 90, 170, 802$$

در مرتب کردن $n$ عنصر با بیش‌ترین طول ارقام $d$ و دامنه ارقام $k$، زمان اجرای الگوریتم برابر $\mathcal{O}(d \cdot (n + k))$ است. اگر ارقام محدود باشند (مثل ده‌دهی) و $d$ عدد کوچکی باشد، این الگوریتم بسیار سریع عمل می‌کند.

radix_sort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void countingSort(vector<int> &arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(arr[i]/exp)%10]++;
 
    for (int i = 1; i < 10; i++)
        count[i] += count[i-1];
 
    for (int i = n-1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
 
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}
 
void radixSort(vector<int> &arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    int exp = 1;
    while(maxVal >= exp) {
        countingSort(arr, exp);
        exp *= 10;
    }
}
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++)
    cin >> arr[i];
    radixSort(arr);
 
    for(int i=0; i<n; i++)
        cout << arr[i] << endl;
 
    return 0;
}

* مرتب‌سازی اعداد با طول ثابت (مثل کد ملی، شماره تلفن).

* مرتب‌سازی رشته‌ها با طول محدود.

* مرتب‌سازی تعداد داده زیاد با دامنه ارقام و تعداد ارقام نسبتاً کوچک.

* https://en.wikipedia.org/wiki/Radix_sort