रेडिक्स सॉर्ट

सॉर्टिंग एल्गोरिदम में रेडिक्स सॉर्ट सबसे अलग है: यह कभी नहीं पूछता कि दो मानों में कौन बड़ा है। यह संख्याओं को अंक-दर-अंक पढ़ता है और दस बकेट की मदद से एक बार में एक अंक के आधार पर सॉर्ट करता है। यह विचार कंप्यूटर से भी पुराना है: पंच कार्ड छाँटने वाली मशीनें इसी तरह काम करती थीं।

0 से 9 तक लेबल वाले दस बकेट की पंक्ति के ऊपर सूची के बार, और एक मान अपने आख़िरी अंक वाले बकेट में गिरता हुआ
0 से 9 तक लेबल वाले दस बकेट की पंक्ति के ऊपर सूची के बार, और एक मान अपने आख़िरी अंक वाले बकेट में गिरता हुआ

विचार

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

बकेट के साथ एक पास

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

एक उदाहरण

170, 45, 75, 90, 802, 24, 2, 66 लें। इकाई के अंक से: 170, 90, 802, 2, 24, 45, 75, 66। दहाई के अंक से: 802, 2, 24, 45, 66, 170, 75, 90; ध्यान दें कि 802 और 2, जिनका दहाई अंक 0 है, पहले पास वाला अपना क्रम बनाए रखते हैं। सैकड़े के अंक से: 2, 24, 45, 66, 75, 90, 170, 802। आठ संख्याओं पर तीन पास: 24 अंक पढ़े गए और 48 मूव, और एक भी तुलना नहीं।

यह कितना तेज़ है?

हर पास हर संख्या का एक अंक पढ़ता है और हर संख्या को दो बार ले जाता है, इसलिए d अंकों वाली n संख्याओं के लिए काम n · d के साथ बढ़ता है। तुलना वाले सॉर्ट को सबसे ख़राब स्थिति में कम से कम लगभग n log₂ n तुलनाएँ चाहिए, क्योंकि उसे n! संभावित क्रमों में एक-एक हाँ-या-ना सवाल से फ़र्क़ करना होता है। रेडिक्स सॉर्ट इससे बँधा नहीं है, क्योंकि यह ऐसे सवाल पूछता ही नहीं। बहुत सी छोटी कुंजियों के लिए, जैसे 1,000 से कम की एक मिलियन संख्याएँ, तीन पास उन लगभग 20 मिलियन तुलनाओं से कहीं कम काम हैं जो तुलना वाले सॉर्ट को चाहिए। लंबी कुंजियों या कम मानों के लिए यह फ़ायदा ख़त्म हो जाता है।

LSD और MSD, और इतिहास

यहाँ दिखाया गया संस्करण सबसे कम महत्वपूर्ण अंक (LSD) से शुरू होता है। उल्टा तरीका, सबसे महत्वपूर्ण अंक पहले (MSD), पहले अंक के आधार पर सूची को बकेट में बाँटता है और हर बकेट को अलग से सॉर्ट करता है, जो अलग-अलग लंबाई की स्ट्रिंग के लिए ठीक रहता है। रेडिक्स सॉर्टिंग की शुरुआत उन पंच कार्ड सॉर्टर से होती है जो 1890 की अमेरिकी जनगणना के लिए बनी Herman Hollerith की टैब्युलेटिंग मशीनों के बाद आए: सॉर्टर हर कार्ड को एक कॉलम के छेद के आधार पर दस खानों में से एक में गिराता था, और ऑपरेटर आख़िरी कॉलम से शुरू करके हर कॉलम के लिए एक बार पूरी गड्डी चलाते थे।

कंप्यूटर इतिहास संग्रहालय में होलेरिथ पंच-कार्ड सारणीयन मशीन, 1890 की अमेरिकी जनगणना में प्रयुक्त प्रकार की। ऑपरेटर एक गड्डी को प्रत्येक स्तंभ के लिए एक बार सॉर्टर से गुजारते थे, जो रेडिक्स सॉर्ट का पूर्वज है।
कंप्यूटर इतिहास संग्रहालय में होलेरिथ पंच-कार्ड सारणीयन मशीन, 1890 की अमेरिकी जनगणना में प्रयुक्त प्रकार की। ऑपरेटर एक गड्डी को प्रत्येक स्तंभ के लिए एक बार सॉर्टर से गुजारते थे, जो रेडिक्स सॉर्ट का पूर्वज है।

इसे आज़माएँ

ऐप खोलें और आगे दबाएँ। हर पास पहले अंक गिनता है, जिससे सूची के नीचे वाली पंक्ति में 0 से 9 तक के बकेट तय हो जाते हैं। फिर संख्याएँ एक-एक करके अपने बकेट में गिरती हैं, सक्रिय बकेट हाइलाइट होता है, और फिर वे वापस कॉपी होती हैं। तीनों पास देखने के लिए 999 तक की अपनी संख्याएँ लिखें, जैसे ऊपर वाला उदाहरण।

अक्सर पूछे जाने वाले प्रश्न

रेडिक्स सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?

किसी तय आधार में d अंकों वाली n कुंजियों के लिए O(n · d), साथ में हर पास के बकेट की लागत। इसे उस बफ़र के लिए O(n) अतिरिक्त मेमोरी चाहिए जिसमें बकेट रहते हैं।

क्या रेडिक्स सॉर्ट स्टेबल है?

LSD रेडिक्स सॉर्ट को स्टेबल होना ही पड़ता है: यह सिर्फ़ इसलिए काम करता है क्योंकि हर पास एक जैसे अंक वाले मानों को उसी क्रम में रखता है जिसमें वे आए। इसलिए अंतिम परिणाम भी स्टेबल होता है।

क्या रेडिक्स सॉर्ट ऋणात्मक संख्याएँ या दशमलव संभाल सकता है?

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

आधार 10 ही क्यों?

क्योंकि इसे समझना आसान है। कंप्यूटर आमतौर पर एक बार में 8 या 16 बिट से सॉर्ट करते हैं, इसलिए 32-बिट संख्या में चार या दो पास लगते हैं, 256 या 65,536 बकेट के साथ।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

रेडिक्स सॉर्ट आज़माएँ