मूलांक अनुक्रमण (रेडिक्स सॉर्ट)

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

रेडिक्स सॉर्ट उस तरह के डेटा पर लगाया जा सकता है जिसे कोशक्रमानुसार जमाया जा सके, वे पूर्णांक, शब्द, पंच कार्ड, ताश, या मेल हो सकते है।

इतिहास

रेडिक्स सॉर्ट पहली बार हर्मन होलेरिथ (Herman Hollerith )द्वारा किए गए टेबुलेटिंग मशीन(tabulating machines) पर के कार्य में पाया गया था। रेडिक्स सॉर्टिंग एल्गोरिदम 1923 की शुरुआत में पंच कार्डों को सॉर्ट करने के तरीके के रूप में आम उपयोग में आया।

पहला मेमोरी-कुशल कंप्यूटर एल्गोरिथ्म 1954 में हेरोल्ड एच. सेवार्ड(Harold H. Seward)द्वारा एमआईटी में विकसित किया गया था। अज्ञात आकार के समुह के चर आवंटन की कथित आवश्यकता के कारण कम्प्यूटरीकृत मूलांक प्रकार को पहले अव्यवहारिक माना गया था। सेवार्ड का नवाचार पहले से आवश्यक समुह का परिमाण और ऑफसेट को निर्धारित करने के लिए एक रेखीय स्कैन का उपयोग करना था, जिससे सहायक मेमोरी का एक ही स्थिर आवंटन हो सके। रैखिक स्कैन, सेवार्ड के अन्य एल्गोरिथ्म - काउंटिंग साॅर्ट(counting sort) से निकटता से संबंधित है।

आधुनिक युग में, रेडिक्स सॉर्ट का उपयोग बाइनरी स्ट्रिंग और पूर्णांकों के संग्रह पर अधिक लागू होता है। बहुत से अव्वल परिणामों में रेडिक्स सॉर्ट दूसरी शॉपिंग तकनीको से 50% से लेकर पुणे से 3 गुना ज्यादा तक तक तेज़ साबित हुआ है ।

एक आईबीएम कार्ड सॉर्टर punched card के एक बड़े सेट पर एक रेडिक्स सॉर्ट का प्रदर्शन करतेे हुये। कार्ड को ऑपरेटर की ठोड़ी के नीचे एक हॉपर में खिलाया जाता है और कार्ड पर एक कॉलम में छिद्रित डेटा के आधार पर मशीन के 13 आउटपुट बास्केट में से एक में सॉर्ट किया जाता है। इनपुट हॉपर के पास वाली क्रैंक का उपयोग रीड हेड को अगले कॉलम पर ले जाने के लिए किया जाता है जैसे कि छँटाई होती है। बैक में रैक पिछले सॉर्टिंग पास से कार्ड रखता है।

अंक क्रम

रेडिक्स सॉर्ट को सबसे महत्वपूर्ण अंक (MSD) या कम से कम महत्वपूर्ण अंक (LSD) से शुरू किया जा सकता है।

उदाहरणः- 1234 के साथ हम, 1 (MSD) या 4 (LSD) से रेडिक्स सॉर्ट को शुरू कर सकते है।

LSD रेडिक्स सॉर्ट आमतौर पर निम्नलिखित छँटाई क्रम का उपयोग करते हैं:

छोटी कुंजियाँ बडी कुंजियों से पहले आती हैं, और फिर उसी लंबाई की कुंजियाँ कोशक्रमानुसार क्रमबद्ध होती हैं। यह पूर्णांक अभ्यावेदन के सामान्य क्रम के साथ मेल खाता है, जैसे अनुक्रम [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] । LSD प्रकार का रेडिक्स सॉर्ट आम तौर पर स्थिर प्रकार का होता हैं ।

MSD रेडिक्स सॉर्ट, स्ट्रिंग्स या निश्चित लंबाई के पूर्णांकों निरूपण के लिए सबसे उपयुक्त हैं। जैसे अनुक्रम [b, c, e, d, f, g, ba] का क्रमबद्ध रुप है-[b, ba, c, d, e, f, g]। यदि कोशक्रमानुसार क्रमबद्धता का उपयोग बेस -10 में वैरिएबल-चौडाई के पूर्णांक को सॉर्ट करने के लिए किया जाता है, तो 1 से 10 तक की संख्याएँ [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] के रूप में आउटपुट होंगी। यदि एक से अधीक बाार उपस्थित कुंजियों के मूल क्रम को हमेशा बनाए रखा जाना चाहिए, तो MSD रेडिक्स सॉर्ट आवश्यक रूप से स्थिर प्रकार का नहीं होता हैं।

ट्रैवर्सल क्रम के अलावा, LSD और MSD सॅार्ट्स मे कुन्जी की चर लंबाई को नियंत्रण करनेे की तकनीक भी भिन्न होती हैं। LSD सॉर्ट पहले लंबाई के आधार पर समूह बनाता है, प्रत्येक समूह को रेडिक्स सॉर्ट करता है, फिर आकार क्रम में समूहों को समेटता है। MSD सॉर्ट को पहले सभी छोटी कुंजी को प्रभावी रूप से सबसे बड़ी कुंजी कि चौडाई के बराबर 'विस्तारित' करना होता है और उनके अनुसार क्रमबद्ध करना होगा, जो कि LSD द्वारा आवश्यक समूहीकरण की तुलना में अधिक जटिल हो सकता है।

हालांकि, MSD सॉर्ट उपखंड और पुनरावृत्ति के लिए अधिक संशोधनीय हैं। MSD सा़ॅर्ट द्वारा हर चरण मे बनाये गये प्रत्येक समुह को अगले चरण में बनाए गए किसी भी अन्य समुह के संदर्भ के बिना, अगले सबसे महत्वपूर्ण अंक का उपयोग करके खुद को मूलांक के आधार पर क्रमबद्ध किया जा सकता है। एक बार अंतिम अंक तक पहुँचने के बाद, समुहों को समेटना ही शेष होता है।

उदाहरण

कम से कम महत्वपूर्ण अंक

इनपुट सूची (आधार 10):

[170, 45, 75, 90, 2, 802, 2, 66]

सबसे दाहिने (अंतिम) अंक से शुरू होकर, उस अंक के आधार पर संख्याओं को क्रमबद्ध करें:

[{170, 90}, {02, 802, 02}, {45, 75}, {66}]

ध्यान दें कि दो 2 के लिए एक 0 का उपयोग किया गया है ताकि 802 अपने सापेक्ष क्रम को बनाए रखे, जैसा कि दूसरी सूची की योग्यता के आधार पर पिछली सूची में रखा गया है (अर्थात दूसरे 2 से पहले रखा गया है)।

अगले बाएं अंक द्वारा छंटनी:

[{02, 802, 02}, {45}, {66}, {170, 75}, {90}]

और अंत में सबसे बाईं ओर के अंक:

[{002, 002, 045, 066, 075, 090}, {170}, {802}]

प्रत्येक चरण को डेटा पर सिर्फ एक पास की आवश्यकता होती है, क्योंकि किसी भी तत्व को किसी अन्य तत्व से तुलना किए बिना उसके समुह में रखा जा सकता है।

कुछ रेडिक्स सॉर्ट के कार्यान्वयन पहले एक समुह में जाने वाले तत्वो की संखा को गिनकर समुह के लिए स्थान आवंटित कर देते हैं। प्रत्येक अंक में होने वाली संख्या एक सरणी में संग्रहीत होती है।

कुछ कार्यान्वयन सरणी के बजाय गतिशील मेमोरी आवंटन का उपयोग करने का विकल्प चुनते हैं।

सबसे महत्वपूर्ण अंक, आगे पुनरावर्ती

इनपुट सूची, अग्रणी शून्य के साथ निश्चित चौड़ाई के अंक:

[170, 045, 075, 025, 002, 024, 802, 066]

पहला अंक, कोष्ठक मे एक समुह के अंक:

[{045, 075, 025, 002, 024, 066}, {170}, {802}

ध्यान दें कि 170 और 802 पहले से ही पूर्ण हैं क्योंकि वे उनके समुह मे अकेले हैं, इसलिए आगे की पुनरावृत्ति की आवश्यकता नहीं है'

अगला अंक:

[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802]

अंतिम अंक:

[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802]

जो कुछ भी शेष है, वह है:

[002, 024, 025, 045, 066, 075, 170, 802]

जटिलता और प्रदर्शन

रेडिक्स सॉर्ट O(nw) समय में संचालित होता है, जहां n कुंजी की संख्या है, और w कुंजी की लंबाई है। LSD प्रकार मे 'औसत कुंजी लंबाई' - w के लिए एक निचला बाउंड प्राप्त किया जा सकता हैं जब चर लंबाई वाली कुंजियों को समुह मे विभाजित किया जाये जैसे ऊपर के भाग मे बताया गया हैं।

बड़े कुंजी आकार LSD कार्यान्वयन में बाधा डाल सकते हैं जब प्रेरित पास की संख्या अड़चन बन जाती है ।

विशिष्ट प्रकार

इन-प्लेस MSD रेडिक्स सॉर्ट कार्यान्वयन

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

इन-प्लेस एमएसडी बाइनरी-रेडिक्स सॉर्ट को बड़े रेडिक्स तक बढ़ाया जा सकता है और इन-प्लेस क्षमता को बनाए रखा जा सकता है। काउंटिंग सॉर्ट का उपयोग प्रत्येक बिन के आकार और उनके शुरुआती सूचकांक को निर्धारित करने के लिए किया जाता है। स्वैपिंग का उपयोग मौजूदा तत्व को अपने बिन में रखने के लिए किया जाता है, इसके बाद बिन सीमा का विस्तार किया जाता है। चूंकि सरणी तत्वों को स्कैन किया जाता है, डिब्बे को ऊपर छोड़ दिया जाता है और केवल डिब्बे के बीच के तत्वों को संसाधित किया जाता है, जब तक कि पूरे सरणी को संसाधित नहीं किया जाता है और सभी तत्व अपने संबंधित डिब्बे में समाप्त हो जाते हैं। डिब्बे की संख्या का उपयोग मूलांक के समान होता है - जैसे 16-मूलांक के लिए 16 डिब्बे। प्रत्येक पास एक अंक (16-मूलांक के मामले में 4-बिट प्रति अंक) पर आधारित है, जो सबसे महत्वपूर्ण अंक से शुरू होता है। प्रत्येक बिन को फिर से अगले अंक का उपयोग करके संसाधित किया जाता है, जब तक कि सभी अंकों को छँटाई के लिए उपयोग नहीं किया जाता है।

ऊपर के पैराग्राफ में चर्चा किए गए न तो इन-बाइनरी-रेडिक्स सॉर्ट और न ही एन-बिट-रेडिक्स सॉर्ट, स्थिर एल्गोरिदम हैं ।

स्थिर MSD मूलांक क्रमबद्ध कार्यान्वयन

एमएसडी रेडिक्स सॉर्ट को एक स्थिर एल्गोरिथ्म के रूप में लागू किया जा सकता है, लेकिन इनपुट सरणी के समान आकार के मेमोरी बफर के उपयोग की आवश्यकता होती है। यह अतिरिक्त मेमोरी इनपुट बफ़र को पहले सरणी तत्व से अंतिम तक स्कैन करने की अनुमति देता है, और उसी क्रम में सरणी तत्वों को गंतव्य डिब्बे में ले जाता है। इस प्रकार, समान तत्वों को मेमोरी बफर में उसी क्रम में रखा जाएगा, जिस क्रम में वे इनपुट ऐरे में थे। MSD- आधारित एल्गोरिथ्म पुनरावृत्ति के पहले स्तर पर आउटपुट के रूप में अतिरिक्त मेमोरी बफ़र का उपयोग करता है, लेकिन इनपुट रिफ़र के अगले स्तर पर बचने के लिए इनपुट और आउटपुट को स्वैप करता है, आउटपुट परिणाम कॉपी करने के ओवरहेड से बचने के लिए इनपुट बफ़र पर वापस जाता है। प्रत्येक डिब्बे को पुन: संसाधित किया जाता है, जैसा कि इन-प्लेस एमएसडी रेडिक्स सॉर्ट के लिए किया जाता है। अंतिम अंक द्वारा सॉर्ट पूरा हो जाने के बाद, आउटपुट बफर को यह देखने के लिए जांचा जाता है कि क्या यह मूल इनपुट ऐरे है, और यदि यह नहीं है, तो एक कॉपी की जाती है। यदि अंक का आकार ऐसा चुना जाता है कि अंक आकार से विभाजित कुंजी आकार एक सम संख्या है, तो अंत में प्रतिलिपि से बचा जाता है।

हाइब्रिड दृष्टिकोण

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

समानांतर कंप्यूटिंग के लिए आवेदन

ध्यान दें कि इस पुनरावर्ती छंटाई एल्गोरिथ्म में समानांतर कंप्यूटिंग के लिए विशेष रूप से आवेदन है, क्योंकि प्रत्येक डिब्बे को स्वतंत्र रूप से क्रमबद्ध किया जा सकता है। इस स्थिति में, प्रत्येक बिन अगले उपलब्ध प्रोसेसर को दिया जाता है। एक एकल प्रोसेसर का उपयोग प्रारंभ (सबसे महत्वपूर्ण अंक) में किया जाएगा। दूसरे या तीसरे अंक तक, सभी उपलब्ध प्रोसेसर संभवतः लगे होंगे। आदर्श रूप से, जैसा कि प्रत्येक उपखंड पूरी तरह से सॉर्ट किया गया है, कम और कम प्रोसेसर का उपयोग किया जाएगा। सबसे खराब स्थिति में, सभी कुंजियाँ एक-दूसरे के समान या लगभग समान होंगी, जिसके परिणामस्वरूप कुंजियों को क्रमबद्ध करने के लिए समानांतर कंप्यूटिंग का उपयोग करने का कोई फायदा नहीं होगा।

पुनरावृत्ति के शीर्ष स्तर में, समानता का अवसर एल्गोरिथ्म के गिनती प्रकार में है। काउंटिंग बेहद समानांतर है, समानांतर_रिड्‌यूस पैटर्न के लिए उत्तरदायी है, और मेमोरी बैंडविड्थ सीमा तक पहुंचने तक कई कोर में काम को अच्छी तरह से विभाजित करता है। एल्गोरिथ्म के इस हिस्से में डेटा-स्वतंत्र समानता है। हालांकि बाद के पुनरावर्तन स्तरों में प्रत्येक बिन को संसाधित करना डेटा-निर्भर है, हालांकि। उदाहरण के लिए, यदि सभी कुंजियाँ समान मान की होती हैं, तो इसमें किसी भी तत्व के साथ केवल एक बिन होगा, और कोई समानता उपलब्ध नहीं होगी। यादृच्छिक इनपुट के लिए सभी डिब्बे समान रूप से आबादी के पास होंगे और बड़ी संख्या में समानता का अवसर उपलब्ध होगा।

ध्यान दें कि तेजी से समानांतर सॉर्टिंग एल्गोरिदम उपलब्ध हैं, उदाहरण के लिए इष्टतम जटिलता ओ (log ( n )) तीन हंगेरियन और रिचर्ड कोल और बैचर के बिटोनिक मर्ज सॉर्ट में ओ ( एल ) की एल्गोरिदमिकता है। लॉग इन करें ² (एन)), जो सभी के एक CREW- पर तरह मूलांक के लिए एक कम एल्गोरिथम समय जटिलता है बच्चों की गाड़ी । सबसे तेजी से ज्ञात PRAM प्रकार 1991 में डेविड पॉवर्स द्वारा एक समानांतर क्विकॉर्टोर्ट के साथ वर्णित किए गए थे जो CRCW-PRAM पर O (log (n)) समय में n प्रोसेसर के साथ निहित रूप से विभाजन करके, साथ ही साथ एक रेडिक्सशॉट का उपयोग करके संचालित होता है। O ( k ) में एक ही चाल है, जहां k अधिकतम कीलैमुलेट है। हालांकि, न तो PRAM आर्किटेक्चर या एक एकल अनुक्रमिक प्रोसेसर वास्तव में एक तरह से बनाया जा सकता है जो ओ (log ( n )) के रूप में प्रति चक्र लगातार फैन-आउट गेट देरी की संख्या के बिना पैमाने पर बढ़ेगा, ताकि प्रभाव में एक पाइपलाइन्ड संस्करण Batcher के bitonic mergesort और हे की (लॉग (एन)) बच्चों की गाड़ी प्रकार सभी हे हैं (log² (n)) घड़ी चक्र के संदर्भ में, शक्तियां स्वीकार करते हैं कि Batcher उसके समानांतर से फाटक देरी के मामले में कम स्थिर होता है साथ quicksort और ओ (nlog ² ( n )) के की-डायनामिक-स्वतंत्र सॉर्टिंग नेटवर्क के लिए मूलांक सॉर्ट या कोल का मर्ज सॉर्ट करता है ।

ट्राई-आधारित रेडिक्स सॉर्ट

रेडिक्स सॉर्ट एक ट्राई (या मूलांक वृक्ष ) का निर्माण करके पूरा किया जा सकता है, और केवल पत्तियों के मूल्यों को ध्यान में रखते हुए एक पूर्व-क्रम(pre-order) ट्रैवर्सल कर सकत है। यह हीप सोर्ट और हीप डेटा संरचना के बीच संबंध के समान है।

यह सभी देखें

• IBM 80 series Card Sorters
• Other Distribution sorts
• Kirkpatrick-Reisch sorting

बाहरी कड़ियाँ

• High Performance Implementation of LSD Radix sort in JavaScript
• High Performance Implementation of LSD & MSD Radix sort in C# with source in GitHub
• Video tutorial of MSD Radix Sort
• Demonstration and comparison of Radix sort with Bubble sort, Merge sort and Quicksort implemented in JavaScript
• Article about Radix sorting IEEE floating-point numbers with implementation.

  Faster Floating Point Sorting and Multiple Histogramming with implementation in C++

• Pointers to radix sort visualizations
• USort library contains tuned implementations of radix sort for most numerical C types (C99)
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp. 168–179.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7ISBN 0-262-03293-7. Section 8.3: Radix sort, pp. 170–173.
• BRADSORT v1.50 source code
• Efficient Trie-Based Sorting of Large Sets of Strings, by Ranjan Sinha and Justin Zobel. This paper describes a method of creating tries of buckets which figuratively burst into sub-tries when the buckets hold more than a predetermined capacity of strings, hence the name, "Burstsort".
• Open Data Structures - Java Edition - Section 11.2 - Counting Sort and Radix Sort, Pat Morin
• Open Data Structures - C++ Edition - Section 11.2 - Counting Sort and Radix Sort, Pat Morin