डीएए - रेडिक्स सॉर्ट

Radix sortएक छोटी सी विधि है जो बहुत से लोग नाम की एक बड़ी सूची को वर्णमाला करते समय सहजता से उपयोग करते हैं। विशेष रूप से, नामों की सूची को पहले प्रत्येक नाम के पहले अक्षर के अनुसार क्रमबद्ध किया जाता है, अर्थात नामों को 26 वर्गों में व्यवस्थित किया जाता है।

सहज रूप से, कोई अपने सबसे महत्वपूर्ण अंक पर संख्याओं को क्रमबद्ध करना चाहेगा। हालांकि, रेडिक्स सॉर्ट पहले-पहले कम से कम महत्वपूर्ण अंकों को छाँटकर काउंटर-इन्टरनेटिव तरीके से काम करता है। पहली पास पर, सभी नंबरों को कम से कम महत्वपूर्ण अंक पर सॉर्ट किया जाता है और एक सरणी में संयोजित किया जाता है। फिर दूसरे पास पर, पूरे नंबरों को दूसरे कम से कम महत्वपूर्ण अंकों पर फिर से सॉर्ट किया जाता है और एक सरणी में जोड़ा जाता है और इसी तरह।

Algorithm: 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

विश्लेषण

प्रत्येक कुंजी को प्रत्येक अंक के लिए एक बार देखा जाता है (या यदि कुंजी अक्षर हैं तो सबसे लंबी कुंजी)। इसलिए, अगर सबसे लंबी कुंजी हैm अंक और हैं n चाबियाँ, मूलांक क्रम में आदेश हैं O(m.n)।

हालाँकि, अगर हम इन दो मूल्यों को देखें, तो कुंजियों की संख्या की तुलना में कुंजियों का आकार अपेक्षाकृत छोटा होगा। उदाहरण के लिए, यदि हमारे पास छह अंकों की चाबियां हैं, तो हमारे पास एक लाख अलग-अलग रिकॉर्ड हो सकते हैं।

यहां, हम देखते हैं कि कुंजियों का आकार महत्वपूर्ण नहीं है, और यह एल्गोरिथ्म रैखिक जटिलता का है O(n)।

उदाहरण

निम्नलिखित उदाहरण से पता चलता है कि मूलांक सात सात अंकों की संख्या पर कैसे संचालित होता है।

इनपुट	1 सेंट पास	2 एन डी पास	3 rd पास
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

उपरोक्त उदाहरण में, पहला कॉलम इनपुट है। तेजी से महत्वपूर्ण अंकों की स्थिति के बाद शेष कॉलम सूची को क्रमिक रूप से दिखाते हैं। मूलांक सॉर्ट के लिए कोड मानता है कि एक सरणी में प्रत्येक तत्वA का n तत्वों की है d अंक, जहां अंक 1 सबसे कम-क्रम अंक और है d उच्चतम-क्रम अंक है।