র্যাডিক্স সর্ট (Radix Sort) একটি নন-কমপেরেটিভ সোর্টিং অ্যালগরিদম। এই সোর্টিং অ্যালগরিদম ইন্টিজার কি-র ওপর কাজ করে যেসব ডিজিট একই পজিশন এবং ভ্যালু শেয়ার করে সেগুলো গ্রুপ করে। র্যাডিক্স হল একটি নাম্বার সিস্টেমের বেস। আমরা জানি ডেসিমাল সিস্টেমে র্যাডিক্স বা বেস ১০। তাই কিছু ডেসিমাল নম্বর সর্ট করতে হলে ১০টি পজিশনাল বক্স লাগবে সংখ্যা স্টোর করার জন্য।
র্যাডিক্স সর্ট টেকনিকের জটিলতা
সময় জটিলতা: O(nk)
স্পেস জটিলতা: O(n+k)
ইনপুট − আনসর্টেড লিস্ট: 802 630 20 745 52 300 612 932 78 187 আউটপুট − সর্টিংয়ের পর ডেটা: 20 52 78 187 300 612 630 745 802 932
অ্যালগরিদম
radixSort(array, size, maxDigit)
ইনপুট: একটি ডেটা অ্যারে, অ্যারেতে মোট সংখ্যা, সর্বোচ্চ সংখ্যার ডিজিট কাউন্ট।
আউটপুট: সর্টেড অ্যারে।
শুরু
১০টি লিস্ট ডিফাইন করুন পকেট হিসেবে
i := 0 থেকে max-1 পর্যন্ত
m = 10^(i+1)
p := 10^i
j := 0 থেকে n-1 পর্যন্ত
temp := array[j] mod m
index := temp / p
pocket[index].append(array[j])
শেষ
count := 0
j := 0 থেকে radix পর্যন্ত
যতক্ষণ pocket[j] খালি নয়
array[count] := pocket[j]-র প্রথম নোড পাওয়া এবং ডিলিট করা
count := count + 1
শেষ
শেষ
inished
শেষ
উদাহরণ কোড
#include <iostream>
#include <list>
#include <cmath>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void radixSort(int *arr, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> pocket[10];
for(i = 0; i < max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j < n; j++) {
temp = arr[j] % m;
index = temp / p;
pocket[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j < 10; j++) {
while(!pocket[j].empty()) {
arr[count] = *(pocket[j].begin());
pocket[j].erase(pocket[j].begin());
count++;
}
}
}
}
int main() {
int n, max;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
cout << "এলিমেন্টের সর্বোচ্চ ডিজিট দিন: ";
cin >> max;
int arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে ডেটা: ";
display(arr, n);
radixSort(arr, n, max);
cout << "সর্টিংয়ের পর ডেটা: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 10 এলিমেন্টের সর্বোচ্চ ডিজিট দিন: 3 এলিমেন্টগুলো দিন: 802 630 20 745 52 300 612 932 78 187 সর্টিংয়ের আগে ডেটা: 802 630 20 745 52 300 612 932 78 187 সর্টিংয়ের পর ডেটা: 20 52 78 187 300 612 630 745 802 932
