एक सॉर्टिंग एल्गोरिदम एक ऐसा एल्गोरिदम है जो एक सूची के घटकों को एक निश्चित क्रम में रखता है। सबसे अधिक उपयोग किए जाने वाले क्रम संख्यात्मक क्रम और लेक्सिकोग्राफिक क्रम हैं।
रेडिक्स सॉर्ट एक गैर-तुलनात्मक सॉर्टिंग एल्गोरिदम है। रेडिक्स सॉर्ट एल्गोरिदम अनसॉर्टेड सूची के लिए सबसे पसंदीदा एल्गोरिदम है।
यह तत्वों को शुरुआत में समान स्थान मूल्य के व्यक्तिगत अंकों को समूहित करके सॉर्ट करता है। रेडिक्स सॉर्ट का विचार सबसे कम महत्वपूर्ण अंक (LSD) से सबसे महत्वपूर्ण अंक (MSD) तक अंक दर अंक सॉर्ट करना है, उनके बढ़ते/घटते क्रम के अनुसार। रेडिक्स सॉर्ट एक छोटी विधि है जिसका उपयोग कई बार किया जाता है जब नामों की एक बड़ी सूची को वर्णमाला क्रम में लगाया जाता है। विशेष रूप से, नामों की सूची को शुरू में प्रत्येक नाम के पहले अक्षर के अनुसार सॉर्ट किया जाता है, यानी नामों को छब्बीस श्रेणियों में व्यवस्थित किया जाता है।
आइए रेडिक्स सॉर्ट एल्गोरिदम के कामकाज को स्पष्ट रूप से समझने के लिए निम्नलिखित चित्रण की समीक्षा करें। स्पष्ट रूप से, पास/इटरेशन की संख्या उच्चतम व्यक्तिगत संख्या के आकार पर निर्भर करती है।
उपरोक्त उदाहरण में, प्राथमिक कॉलम इनपुट है। शेष कॉलम उत्तरोत्तर महत्वपूर्ण अंक स्थिति पर क्रमिक सॉर्ट के बाद सूची दिखाते हैं।
रेडिक्स सॉर्ट की जटिलता विश्लेषण 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
उदाहरण
यह रेडिक्स सॉर्ट को लागू करने के लिए एक C प्रोग्राम है।
#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("सॉर्ट की जाने वाली वस्तुओं की संख्या दर्ज करें: ");
scanf("%d", &n);
printf("वस्तुएं दर्ज करें: ");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
radix_sort(a, n);
printf("सॉर्ट की गई वस्तुएं: ");
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
