একটি বাছাই অ্যালগরিদম একটি অ্যালগরিদম যা একটি তালিকার উপাদানকে একটি নির্দিষ্ট ক্রমে রাখে। সর্বাধিক ব্যবহৃত অর্ডারগুলি হল সংখ্যাসূচক ক্রম এবং অভিধানিক ক্রম।
Radix সাজানোর একটি অ-তুলনামূলক বাছাই অ্যালগরিদম। রেডিক্স সর্ট অ্যালগরিদম হল সাজানো তালিকার জন্য সবচেয়ে পছন্দের অ্যালগরিদম৷
এটি প্রাথমিকভাবে একই স্থান মানের পৃথক সংখ্যাগুলিকে গোষ্ঠীবদ্ধ করে উপাদানগুলিকে সাজায়৷ রেডিক্স সর্টের ধারণা হল ডিজিট বাই ডিজিট সাজানো নিম্ন উল্লেখযোগ্য ডিজিট (এলএসডি) থেকে শুরু করে সবচেয়ে উল্লেখযোগ্য ডিজিট (এমএসডি) , তাদের ক্রমবর্ধমান/হ্রাস অনুসারে। রেডিক্স বাছাই একটি ছোট পদ্ধতি যা নামের একটি বড় আকারের তালিকার বর্ণমালা করার সময় বেশ কয়েকবার ব্যবহার করা হয়। বিশেষ করে, নামের তালিকা প্রাথমিকভাবে প্রতিটি নামের প্রথম অক্ষর অনুসারে সাজানো হয়, অর্থাৎ নামগুলো ছাব্বিশটি বিভাগে সাজানো হয়।
রেডিক্স সর্ট অ্যালগরিদমের কাজ সম্পর্কে স্পষ্টভাবে বোঝার জন্য আমাদের নিম্নলিখিত চিত্রটি পর্যালোচনা করা যাক। স্পষ্টতই, পাস/পুনরাবৃত্তির সংখ্যা সর্বোচ্চ পৃথক সংখ্যার আকারের উপর নির্ভর করে।
উপরের উদাহরণে, প্রাথমিক কলামটি ইনপুট। অবশিষ্ট কলামগুলি ক্রমবর্ধমান তাৎপর্যপূর্ণ সংখ্যার অবস্থানে ধারাবাহিক সাজানোর পরে তালিকা দেখায়৷
Radix Sort O(m.n) এর জটিলতা বিশ্লেষণ।
যাইহোক, যদি আমরা এই 2টি মানগুলির দিকে তাকাই, কীগুলির সংখ্যার তুলনায় কীগুলির আকার তুলনামূলকভাবে ছোট। উদাহরণ হিসেবে, যদি আমাদের কাছে ছয়-সংখ্যার কী থাকে, তাহলে আমাদের 1,000,000 সম্পূর্ণ ভিন্ন রেকর্ড থাকতে পারে।
এখানে, আমরা দেখতে চাই যে কীগুলির আকার গুরুত্বপূর্ণ নয় এবং এই অ্যালগরিদমটি রৈখিক মানের O(n)
অ্যালগরিদম
Radix_sort (list, n) shift = 1 for loop = 1 to keysize do for entry = 1 to n do bucketnumber = (list[entry].key / shift) mod 10 append (bucket[bucketnumber], list[entry]) list = combinebuckets() shift = shift * 10
উদাহরণ
এটি রেডিক্স সাজানোর জন্য একটি সি প্রোগ্রাম৷
৷#include<stdio.h>
int get_max (int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n){
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0){
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++){
for (i = 0; i < 10; i++){
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++){
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++){
for (j = 0; j < bucket_cnt[k]; j++){
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
int main (){
int i, n, a[10];
printf ("Enter the number of items to be sorted: ");
scanf ("%d", &n);
printf ("Enter items: ");
for (i = 0; i < n; i++){
scanf ("%d", &a[i]);
}
radix_sort (a, n);
printf ("Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
return 0;
} আউটপুট
Enter number of items to be sorted 6 Enter items:567 789 121 212 563 562 After pass 1 : 121 212 562 563 567 789 After pass 2 : 212 121 562 563 567 789 After pass 3 : 121 212 562 563 567 789 Sorted items : 121 212 562 563 567 789
