রাডিক্স সোর্ট একটি নন-কম্প্যারেটিভ সোর্টিং অ্যালগরিদম। এটি ইন্টিজার কি-তে কাজ করে ডিজিট গ্রুপিং করে। রাডিক্স = সংখ্যা পদ্ধতির বেস (দশমিকের জন্য ১০)। দশমিক সংখ্যা সোর্ট করতে ১০টি পজিশনাল বক্স (পকেট) লাগে।
রাডিক্স সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: O(nk) (k = ম্যাক্সিমাম ডিজিট সংখ্যা)
- স্পেস কমপ্লেক্সিটি: O(n + k)
ইনপুট এবং আউটপুট
Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output: Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932
অ্যালগরিদম
radixSort(array, size, maxDigit)
Begin
10টি পকেট (লিস্ট) ডিফাইন করুন
for i := 0 to max-1 do
m = 10^(i+1), p = 10^i
for j := 0 to n-1 do
temp = array[j] % m
index = temp / p
pocket[index].append(array[j])
done
count := 0
for j := 0 to 9 do
while pocket[j] not empty:
array[count] = pocket[j] থেকে প্রথম নোড রিমুভ
count++
done
done
done
End
C++ উদাহরণ
#include <iostream>
#include <list>
#include <cmath>
using namespace std;
void display(int *a, int n) { for(int i=0;i> n;
cout << "Enter the maximum digit of elements: "; cin >> max;
int arr[n];
cout << "Enter elements:" << endl;
for(int i=0; i> arr[i];
cout << "Data before Sorting: "; display(arr, n);
radixSort(arr, n, max);
cout << "Data after Sorting: "; display(arr, n);
}
আউটপুট
Enter the number of elements: 10
Enter the maximum digit of elements: 3
Enter elements: 802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932
