🧣 🧚🏽 📖 अमेरिकी ध्वज क्रमबद्ध 👨‍👨‍👧‍👧 👿 🎠

इस "मल्टीबैंड" सॉर्टिंग के संचालन के सिद्धांत को समझने के लिए, तीन पट्टियों के साथ एक ध्वज के उदाहरण के साथ शुरुआत करना आसान है। और तीन रंगों के झंडे के साथ आसानी से निपटने के लिए, पहले यह देखना बेहतर है कि यह दो-रंग के उदाहरण के साथ कैसे काम करता है। ~~और दो रंगों से निपटने के लिए ...~~

यह लेख EDISON के समर्थन से लिखा गया था।

हम सॉफ्टवेयर के पोर्टिंग और माइग्रेशन में लगे हुए हैं, साथ ही मोबाइल एप्लिकेशन एंड्रॉइड और आईओएस के विकास के लिए भी ।

हम एल्गोरिदम के सिद्धांत से प्यार करते हैं! ;-)

दो रंग का झंडा

सबसे पहले, उस मामले पर विचार करें जब क्रमबद्ध सरणी में संख्याएं केवल दो बिट्स में वितरित की जाती हैं। सादगी के लिए, हम मानते हैं कि हमारे पास शून्य (कम क्रम) और लोगों (उच्च क्रम) की एक सरणी है।

इस प्रकार, हमारे पास केवल दो "बैंड" हैं: एक में हम कम से कम महत्वपूर्ण बिट्स (शून्य) को स्थानांतरित करेंगे, और अन्य उच्चतम बिट्स (इकाइयों) में। कोई भी दो रंगों वाला झंडा प्रदर्शन के लिए जाएगा। उदाहरण के लिए, यूक्रेन का झंडा।

यहाँ क्या हो रहा है? चूंकि पहले चरण में यह ज्ञात नहीं है कि हमारे पास कितने शून्य और कितनी इकाइयाँ हैं, इसलिए यह स्पष्ट नहीं है कि प्रत्येक "बैंड" का आकार क्या होगा। इसलिए, हम दो बिंदुओं को सरणी की कुंजी पर रखते हैं। कम क्रम के लिए, सूचक उच्च क्रम के लिए, सरणी की शुरुआत में सेट किया गया है - अंत तक। फिर हम बाएं से दाएं सरणी के माध्यम से एक एकल पास बनाते हैं और प्रत्येक बिट तत्व को देखते हैं।

यदि मार्ग के दौरान एक तत्व उच्चतम क्रम के बराबर है, तो दूसरा सूचक हमें बताता है कि इस तत्व को कहां स्थानांतरित करना है (हम एक विनिमय करते हैं)। अगला तत्व बाईं ओर ले जाने के लिए पॉइंटर, वरिष्ठ अंक के लिए "स्ट्रिप" का विस्तार हुआ है।

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

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

डच राष्ट्रीय ध्वज समस्या :: डच राष्ट्रीय ध्वज समस्या

हम कार्य को थोड़ा जटिल करते हैं, दो अंकों पर नहीं, तीन पर विचार करते हैं। मान लें कि ऐरे के तत्व सबसे कम (शून्य), मध्य (यूनिट) और सीनियर (दो) अंकों के हैं।

प्रदर्शन के लिए, हम ~~फ्रांस~~ के तीन-लाल-सफेद-नीले झंडे , ~~रूस के~~ ~~लक्समबर्ग~~ , ~~नीदरलैंड के~~ ~~श्लेस्विग-गोल्डस्टीन को~~ लेते हैं। नीदरलैंड का झंडा आखिर क्यों? क्योंकि इस ध्वज के उदाहरण पर अपने व्याख्यानों में एद्गर दिज्कस्ट्रा ने संबंधित एल्गोरिथम की जांच की, जिसे "डच राष्ट्रीय ध्वज का कार्य" कहा जाता था।

जैसा कि आप देख सकते हैं, विशेष रूप से नया कुछ भी नहीं है। प्रत्येक श्रेणी का अपना सूचक होता है। प्रारंभ में, जूनियर और मध्य के लिए लेबल सरणी की शुरुआत में शुरुआती स्थिति लेते हैं और जब संबंधित तत्व का सामना करते हैं तो दाईं ओर जाते हैं। उच्च क्रम के लिए सूचक पहले सरणी के अंत में है और बाईं ओर चलता है।

सरणी से गुजरना वास्तव में भी अधूरा होगा, अगर बिट्स को कम या ज्यादा समान रूप से वितरित किया जाता है, तो एल्गोरिथ्म इसके "बैंड" में सभी तत्वों को बिखेरने से पहले सरणी के 2/3 से गुजर जाएगा।

अमेरिकी ध्वज प्रकार :: अमेरिकी ध्वज प्रकार

अब, हमारे स्पष्टीकरण में, हम मल्टीबैंड अमेरिकी ध्वज पर आगे बढ़ सकते हैं।

जब हमारे पास दो नहीं, तीन नहीं, बल्कि कितने भी अंक हों, हम तय करते हैं कि प्रत्येक अंक कहां से शुरू होना चाहिए (इसका "बैंड") और तत्वों को उनके "बैंड" में फिर से लिखना।

इस एल्गोरिथ्म में, संख्याओं को आमतौर पर दशमलव के रूप में नहीं माना जाता है, लेकिन एक अलग बिट गहराई में, अक्सर दो की शक्ति होती है। अक्सर संख्या 256 को बिट डेप्थ (कुछ हद तक कम से कम 128) के आधार के रूप में लिया जाता है, जो आपको स्ट्रिंग्स की व्यवस्था करने के लिए कुशलतापूर्वक छंटाई करने की अनुमति देता है। बिट गहराई के लिए संख्याओं के लिए, छोटे 2 ^एन (2, 4, 16, आदि) लेने के लिए यह अधिक सुविधाजनक है, जो आपको दशमलव संख्याओं की तुलना करते हुए एक शक्ति को बढ़ाने के बजाय बिट्स द्वारा स्थानांतरण करने की अनुमति देता है।

एनीमेशन आधार 16 के साथ थोड़ी गहराई का एक उदाहरण दिखाता है:

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

अनुमानित वितरण के साथ गिनती के प्रकार के बारे में लेख में , एक समान रूप से एक समान एल्गोरिथ्म है - सन्निकटन छँटाई । वहां हमने गिना कि सरणी में प्रत्येक संख्या कितनी बार हुई है - और प्राप्त स्थानीयकरण के अनुसार तत्वों का पुनर्वितरण किया गया है। यहाँ हम गिनते हैं कि श्रेणी में प्रत्येक अंक कितनी बार सबर्रे तत्वों के लिए होता है - और हम सबर्रे में तत्वों को प्राप्त स्थानीयकरण के अनुसार पुनर्वितरित भी करते हैं। यदि सन्निकटन एक प्रकार की गिनती है, तो "अमेरिकी" गिनती-छँटाई है।

अमेरिकी ध्वज क्रमबद्ध - पायथन कार्यान्वयन

#           def get_radix_val(x, digit, radix) -> int: return int(floor(x / radix**digit)) % radix #             def compute_offsets(a_list, start: int, end: int, digit, radix) -> list: #          counts = [0 for _ in range(radix)] for i in range(start, end): #        #         val = get_radix_val(a_list[i], digit, radix) counts[val] += 1 #       #          offsets = [0 for _ in range(radix)] sum = 0 #         for i in range(radix): offsets[i] = sum sum += counts[i] return offsets #      def swap(a_list, offsets, start: int, end: int, digit, radix) -> None: i = start #          next_free = copy(offsets) #        #   (       ) cur_block = 0 while cur_block < radix-1: # if i >= start + offsets[cur_block+1]: cur_block += 1 continue radix_val = get_radix_val(a_list[i], digit, radix) if radix_val == cur_block: i += 1 continue swap_to = next_free[radix_val] a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i] next_free[radix_val] += 1 #   def american_flag_sort_helper(a_list, start: int, end: int, digit, radix) -> None: #          offsets = compute_offsets(a_list, start, end, digit, radix) #      swap(a_list, offsets, start, end, digit, radix) if digit == 0: #     ? return #   #       for i in range(len(offsets)-1): #      #         american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix) #   def american_flag_sort(a_list, radix) -> None: #,         for x in a_list: assert(type(x) == int) #    max_val = max(a_list) #    (  ) max_digit = int(floor(log(max_val, radix))) #   -     american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)

Ska सॉर्ट :: Ska सॉर्ट

जर्मन प्रोग्रामर, माल्टे स्कारुपके ने घोषणा की कि उन्होंने एक नया छँटाई एल्गोरिथ्म विकसित किया है, जो कि मौलिक रूप से "अमेरिकी ध्वज" और बेहतर प्रदर्शन करने वाला std है :: औसतन 2 बार छांटना (std :: सॉर्ट - एक एल्गोरिथ्म जिसे आत्मनिरीक्षण छँटाई के लिए भी जाना जाता है। - ढेर से त्वरित छंटाई और छंटाई का एक संकर)।

सरणी को पुनरावर्ती रूप से सॉर्ट किया जाता है, पुनरावृत्ति के पहले स्तर पर, पूरे सरणी को एक सबर्रे के रूप में लिया जाता है।
यदि सबर्रे में 128 से कम तत्व हैं, तो इसके लिए std :: सॉर्ट कहा जाता है।
यदि सबर्रे में 128 से 1024 तत्व शामिल हैं, तो इसके लिए अमेरिकी ध्वज छंटाई कहा जाता है।
यदि एक उपश्रेणी में 1024 से अधिक तत्व हैं, तो इसके लिए स्की सॉर्टिंग कहा जाता है।
इसके अलावा, सबसे खराब स्थिति से बचने के लिए, यदि पुनरावर्ती घोंसला बहुत बड़ा है (16 से अधिक स्तर), एल्गोरिथ्म एसटीडी :: सॉर्ट करने के लिए स्विच करता है, भले ही सबर्रे में 128 से अधिक तत्व हों।

जाहिर है, यह एक बहुत ही प्रभावी एल्गोरिथ्म है और एक ही समय में बेहद जटिल है - इसके लेखक के कार्यान्वयन में लगभग डेढ़ हजार लाइनें लगती हैं। शायद हम किसी दिन इस छंटाई पर विचार करेंगे, अब हम इसमें नहीं जाएंगे। इच्छुक लोग नीचे दिए गए लिंक पर क्लिक कर सकते हैं।

संदर्भ

डच राष्ट्रीय ध्वज समस्या , अमेरिकी ध्वज प्रकार

स्की प्रकार:

मैंने लिखा एक तेज़ सॉर्टिंग एल्गोरिथम ( भाग 1 , भाग 2 )

गिथब कोड

श्रृंखला लेख:

एक्सेल आवेदन AlgoLab.xlsm
एक्सचेंज सॉर्ट
निवेशन शॉर्ट्स
चयन के आधार पर छाँटें
मर्ज करना
वितरण के आधार पर छाँटें
- अनुमानित वितरण के साथ गिनती
- अमेरिकी ध्वज क्रमबद्ध
- बिटवाइज़ सॉर्टिंग में प्रत्यय का पेड़
- वितरण द्वारा छंटाई तुलना
हाइब्रिड सॉर्टिंग

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