الگوریتم مرتب سازی پایه ای (Radix Sort)
الگوریتم مرتب سازی پایه ای (Radix Sort) یا مبنایی یکی دیگر از الگوریتم های مرتب سازی است که لیستی با طول ثابت و تعداد عناصر k را در زمان O(kn) مرتب می کند. در این الگوریتم روش کار به این صورت است که ورودی را به بخش های کوچک تقسیم می کنیم (اگر ورودی عدد باشد، به رقم ها و اگر رشته باشد به کاراکترها) و آرایه را بر اساس ارزش بیت ها (رقم یا کاراکتر) از کم ارزش ترین بیت به پر ارزش ترین بیت مرتب می کنیم. به این ترتیب آرایه ما پس از طی k مرحله مرتب می شود.
پیاده سازی Radix Sort
در زیر می توانید نحوه پیاده سازی الگوریتم Radix Sort با زبان سی پلاس پلاس را مشاهده کنید:
// C++ implementation of Radix Sort #include<iostream> using namespace std; // A utility function to get maximum value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. void countSort(int arr[], int n, int exp) { int output[n]; // output array int i, count[10] = {0}; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[ (arr[i]/exp)%10 ]++; // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; count[ (arr[i]/exp)%10 ]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that instead // of passing digit number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m/exp > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array void print(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Driver program to test above functions int main() { int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; int n = sizeof(arr)/sizeof(arr[0]); radixsort(arr, n); print(arr, n); return 0; }
امتحان کنید
خروجی:
2 24 45 66 75 90 170 802
نکات
- پیچیدگی زمانی این الگوریتم برابر است با O(nk).
- پیچیدگی فضایی این الگوریتم برابر است با O(n+k).
نوشته الگوریتم مرتب سازی پایه ای (Radix Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.