इस सिद्धांत के अनुसार मर्ज कार्य करें:

1. ऑर्डर किए गए सबरेज़ खोजे जाते हैं (एक विकल्प के रूप में - बनते हैं)।
2. आदेशित उप-प्रजातियां एक सामान्य क्रमबद्ध उप-श्रेणी में सम्‍मिलित हैं।

अपने आप से, सरणी के अंदर किसी भी आदेशित सबरे का अधिक मूल्य नहीं है। लेकिन अगर किसी ऐरे में हम दो ऑर्डर किए गए सबरेज़ पाते हैं, तो यह पूरी तरह से अलग मामला है। तथ्य यह है कि आप उन्हें बहुत जल्दी और कम से कम लागत पर मर्ज कर सकते हैं - एक सामान्य ऑर्डर किए गए सबरेज़ की एक जोड़ी से एक सामान्य ऑर्डर किए गए सबर्रे बनाने के लिए।



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

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


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

प्राकृतिक न्यूमैन फ्यूजन

नेमन एल्गोरिदम 40 के दशक के कंप्यूटरों की डिज़ाइन सुविधाओं से प्रभावित था। ऐसा लग रहा था:

1. कुल में, तीन चुंबकीय टेप का उपयोग किया जाता है - मुख्य एक, जिस पर अनसोल्ड डेटा और दो सहायक डेटा दर्ज किए जाते हैं।
2. डेटा मुख्य टेप से क्रमिक रूप से पढ़ा जाता है।
3. जबकि क्रमिक रूप से पढ़ा जाने वाला डेटा एक आदेशित सबरे है, उन्हें सहायक टेप में से एक में कॉपी किया जाता है।
4. जैसे ही अगला सॉर्ट किया गया सबरे पूरा हो जाता है (यानी, पिछले टेप से छोटा एक तत्व मुख्य टेप पर पाया जाता है), एक पॉइंटर को सहायक टेप (सबरे के अंत) पर रखा जाता है और दूसरे सहायक टेप में स्विच होता है।
5. अंक 2-4 को फिर से दोहराया जाता है, केवल डेटा को दूसरे सहायक टेप में स्थानांतरित किया जाता है। अगले ऑर्डर किए गए सबर्रे के अंत में, मुख्य टेप वैकल्पिक रूप से एक सहायक टेप पर स्विच करता है, फिर दूसरे में।
6. जब मुख्य टेप के सभी डेटा को पढ़ा गया है, तो सहायक टेप का प्रसंस्करण होता है।
7. दोनों सहायक टेप बदले में डेटा पढ़ते हैं।
8. इस मामले में, दो टेपों के अगले डेटा की एक दूसरे के साथ तुलना की जाती है। तुलना परिणामों के अनुसार, जोड़े का सबसे छोटा तत्व मुख्य टेप पर दर्ज किया गया है।
9. चूंकि सहायक टेपों पर सरणियों की सीमा को संकेत के साथ चिह्नित किया जाता है, इसलिए रीडिंग और तुलना केवल सॉर्ट किए गए सबरेज़ के भीतर होती है।
10. यदि सहायक टेप में से एक पर अगले उपप्रकार के तत्व खत्म हो जाते हैं, तो शेष टेप से शेष सबर्रे को मुख्य टेप में स्थानांतरित कर दिया जाता है।
11. हम पूरी प्रक्रिया को फिर से दोहराते हैं जब तक कि मुख्य टेप पर डेटा पूरी तरह से ऑर्डर की गई सरणी न हो।

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

इस एल्गोरिथ्म की जटिलता मामूली है - ओ ( एन ² ), और, फिर भी, ट्यूब कंप्यूटिंग के अग्रदूतों के लिए यह एक सफलता थी।

इस पहले मर्ज के प्रकार के उदाहरण पर, एल्गोरिदम के इस वर्ग का एक दोष पहले से ही दिखाई दे रहा है - अतिरिक्त मेमोरी की लागत। इस संबंध में, लगभग सभी मर्ज सॉर्टिंग को अतिरिक्त रूप से O ( n ) की आवश्यकता होती है, हालांकि, सुरुचिपूर्ण अपवाद दुर्लभ हैं।

बोवेस-नेल्सन प्रत्यक्ष विलय

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

1. सरणी को आधे में विभाजित किया गया है - बाएं और दाएं हिस्सों में।
2. तत्वों को समूहों में विभाजित किया गया है।
3. पहली पुनरावृत्ति पर, ये दो तत्व हैं (बाएं आधे का 1 तत्व + दाएं आधे का पहला तत्व, बाएं आधा का दूसरा तत्व + दाएं आधा का दूसरा तत्व, आदि), दूसरा पुनरावृत्ति पर - चार तत्व (1-) तीसरे भाग पर बाएँ आधे + 1 के दूसरे और दूसरे तत्व + दाहिने आधे के तीसरे और चौथे तत्व, तीसरे भाग पर बाएँ आधे + के तीसरे और चौथे तत्व), तीसरे पर - आठ, आदि।
4. बाएं समूह के प्रत्येक समूह के तत्व क्रमबद्ध उप-प्रकार हैं, दाहिने आधे से प्रत्येक समूह के तत्व भी क्रमबद्ध उप-प्रकार हैं।
5. पिछले पैराग्राफ से सॉर्ट किए गए सबरेज़ को मर्ज करें।
6. हम बिंदु 1 पर लौटते हैं। चक्र तब तक जारी रहता है जब तक समूहों का आकार सरणी के आकार से छोटा नहीं हो जाता।

ऐसा लग सकता है कि यहां अतिरिक्त मेमोरी की आवश्यकता है। लेकिन नहीं! एनीमेशन में अधिक समझने योग्य धारणा के लिए, सरणी के बाएं और दाएं हिस्सों को एक-दूसरे पर स्थित किया जाता है, ताकि तुलना की गई उप-श्रेणियों की सापेक्ष स्थिति अधिक स्पष्ट हो। हालांकि, सख्त द्विभाजन के कारण, एक एल्गोरिथ्म संभव है जिसमें मेमोरी से अतिरिक्त संसाधनों को शामिल किए बिना सभी तुलना और आदान-प्रदान किए जाते हैं। जो मर्ज सॉर्टिंग के लिए बहुत ही असामान्य है।

def bose_nelson(data): m = 1 while m < len(data): j = 0 while j + m < len(data): bose_nelson_merge(j, m, m) j = j + m + m m = m + m return data def bose_nelson_merge(j, r, m): if j + r < len(data): if m == 1: if data[j] > data[j + r]: data[j], data[j + r] = data[j + r], data[j] else: m = m // 2 bose_nelson_merge(j, r, m) if j + r + m < len(data): bose_nelson_merge(j + m, r, m) bose_nelson_merge(j + m, r - m, m) return data 

सभी सॉर्टिंग मर्ज में कुछ है जो उन्हें हाइड्रोजन बम के समान बनाता है। पहले विभाजन होता है, फिर संश्लेषण होता है।

संदर्भ

मर्ज / मर्ज

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

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

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

बोवे-नेल्सन की छंटाई के लिए प्रतिबंध है - सरणी का आकार दो की शक्ति होना चाहिए। यदि यह स्थिति पूरी नहीं होती है, तो मैक्रो सरणी को उपयुक्त आकार में फसल देगा।

यह लेख EDISON सॉफ्टवेयर के समर्थन से लिखा गया था, एक कंपनी जो 3D पुनर्निर्माण सॉफ्टवेयर लिखती है और परिष्कृत माप उपकरण विकसित कर रही है ।