रेडिक्स सॉर्ट के लिए सी प्रोग्राम

एक सॉर्टिंग एल्गोरिथम एक एल्गोरिथम है जो एक लिस्टिंग के घटकों को एक निश्चित क्रम में रखता है। सबसे अधिक उपयोग किए जाने वाले आदेश संख्यात्मक क्रम और शब्दावली क्रम हैं।

मूलांक सॉर्ट एक गैर-तुलनात्मक सॉर्टिंग एल्गोरिदम है। रेडिक्स सॉर्ट एल्गोरिथम अक्रमित सूची के लिए सबसे पसंदीदा एल्गोरिथम है।

यह प्रारंभिक रूप से समान स्थान मान के अलग-अलग अंकों को समूहीकृत करके तत्वों को क्रमबद्ध करता है। रेडिक्स सॉर्ट का विचार अंकों के आधार पर अंकों को क्रमबद्ध करना है कम से कम महत्वपूर्ण अंक (एलएसडी) से सबसे महत्वपूर्ण अंक (एमएसडी) तक शुरू करना , उनके बढ़ते / घटते क्रम के अनुसार। रेडिक्स सॉर्ट एक छोटी सी विधि है जिसका उपयोग कई बार नामों की एक बड़ी सूची को वर्णानुक्रम में करने के लिए किया जाता है। विशेष रूप से, नामों की सूची शुरू में प्रत्येक नाम के पहले अक्षर के अनुसार क्रमबद्ध की जाती है, अर्थात नामों को छब्बीस श्रेणियों में व्यवस्थित किया जाता है।

रेडिक्स सॉर्ट एल्गोरिथम की कार्यप्रणाली के बारे में स्पष्ट रूप से समझने के लिए आइए निम्नलिखित उदाहरण की समीक्षा करें। स्पष्ट रूप से, पास/पुनरावृत्ति की संख्या उच्चतम व्यक्तिगत संख्या के आकार पर निर्भर करती है।

उपरोक्त उदाहरण में, प्राथमिक कॉलम इनपुट है। शेष कॉलम लगातार महत्वपूर्ण अंकों की स्थिति पर क्रमिक प्रकार के बाद सूची दिखाते हैं।

रेडिक्स सॉर्ट ओ (एमएन) का जटिलता विश्लेषण।

हालाँकि, यदि हम इन 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 ("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