मर्ज एल्गोरिथम

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

आवेदन

मर्ज सॉर्ट के लिए एक उदाहरण

मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में महत्वपूर्ण भूमिका निभाता है, तुलना-आधारित सॉर्टिंग एल्गोरिदम वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं।

1. पुनरावर्तन (कंप्यूटर विज्ञान) सूची को समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट की स्थिति में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें। 1 आकार के परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
2. जब तक एकल सूची में सभी तत्व सम्मिलित नहीं हो जाते, तब तक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को विलय करें। एकल सूची क्रमबद्ध सूची है।

मर्ज सॉर्ट एल्गोरिथम में मर्ज एल्गोरिथ्म का बार-बार उपयोग किया जाता है।

उदाहरण में मर्ज सॉर्ट का उदाहरण दिया गया है। यह 7 पूर्णांकों की अवर्गीकृत सारणी से प्रारम्भ होता है। सारणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है एवं इसे क्रमबद्ध किया जाता है। तब चयन गए विभाजनों को बड़ा, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 1 विभाजन, क्रमबद्ध सारणी, शेष न रह जाए।

दो सूचियों को विलय करना

दो क्रमबद्ध सूचियों को विलय करना रैखिक समय एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित स्यूडोकोड एल्गोरिथम प्रदर्शित करता है, जो इनपुट सूचियों (या तो लिंक्ड सूचियों या सारणी डेटा संरचना) को विलय करता है, A एवं B नई सूची C में कार्यक्रम head सूची का प्रथम तत्व उत्पन्न करता है; किसी तत्व को त्यागने का अर्थ है कि इसे सूची से सामान्यतः पॉइंटर या इंडेक्स को बढ़ाकर विस्थापित करना है ।

एल्गोरिथम मर्ज (ए, बी) है
    इनपुट ए, बी: सूची
    रिटर्न सूची

    सी: = नई खाली सूची
    जबकि A खाली नहीं है एवं B खाली नहीं है
        अगर सिर (ए) ≤ सिर (बी) तो
            शीर्ष (A) को C से जोड़ें
            ए का सिर गिरा दो
        अन्य
            सिर (बी) को सी में जोड़ें
            बी का सिर गिरा दो

    // अब तक, या तो ए या बी खाली है। यह अन्य इनपुट सूची को खाली करने के लिए बनी हुई है।
    जबकि A खाली नहीं है
        शीर्ष (A) को C से जोड़ें
        ए का सिर गिरा दो
    जबकि B खाली नहीं है
        सिर (बी) को सी में जोड़ें
        बी का सिर गिरा दो

    वापसी सी

जब इनपुट लिंक्ड सूचियाँ हैं, तो इस एल्गोरिथम को केवल कार्य स्थान की एक स्थिर मात्रा का उपयोग करने के लिए लागू किया जा सकता है; सूचियों के नोड्स में पॉइंटर्स को बहीखाता पद्धति के लिए एवं अंतिम मर्ज की गई सूची के निर्माण के लिए पुन: उपयोग किया जा सकता है।

मर्ज सॉर्ट एल्गोरिथम में, यह सबरूटीन सामान्यतः दो उप-सरणियों को मर्ज करने के लिए उपयोग किया जाता है A[lo..mid], A[mid+1..hi] एकल सारणी का A. यह उप-सरणियों को एक अस्थायी सारणी में कॉपी करके, फिर ऊपर मर्ज एल्गोरिथ्म को लागू करके किया जा सकता है। एक अस्थायी सारणी के आवंटन से बचा जा सकता है, लेकिन गति एवं प्रोग्रामिंग आसानी की कीमत पर। विभिन्न इन-प्लेस मर्ज एल्गोरिदम तैयार किए गए हैं, कभी-कभी उत्पादन करने के लिए रैखिक-समयबद्धता का त्याग करना O(n log n) कलन विधि; देखना Merge sort § Variants चर्चा के लिए।

के-वे मर्जिंग

Main article: K-way merge algorithm

k-वे मर्जिंग बाइनरी मर्जिंग को मनमाना संख्या में सामान्यीकृत करता है k क्रमबद्ध इनपुट सूचियों की। के आवेदन k-वे मर्जिंग विभिन्न सॉर्टिंग एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य सॉर्टिंग भी सम्मिलित है एवं एक बाहरी छँटाई एल्गोरिथ्म जो इसके इनपुट को विभाजित करता है k = 1/M − 1 ब्लॉक जो मेमोरी में फिट होते हैं, इन्हें एक-एक करके सॉर्ट करते हैं, फिर इन ब्लॉक्स को मर्ज कर देते हैं।

इस समस्या के कई समाधान मौजूद हैं। एक भोली समाधान के ऊपर एक लूप करना है k प्रत्येक बार न्यूनतम तत्व चुनने के लिए सूचीबद्ध करता है, एवं इस लूप को तब तक दोहराता है जब तक कि सभी सूचियां खाली न हो जाएं:

• इनपुट: की एक सूची k सूचियाँ।
• जबकि कोई भी सूची खाली नहीं है:
  • न्यूनतम पहले तत्व वाले को खोजने के लिए सूचियों पर लूप करें।
  • न्यूनतम तत्व को आउटपुट करें और इसे उसकी सूची से हटा दें।

सबसे अच्छा, सबसे खराब एवं औसत मामला, यह एल्गोरिथ्म प्रदर्शन करता है (k−1)(n−k/2)तत्वों की तुलना अपने कार्य को करने के लिए की जाती है तो कुल मिलाकर n सूचियों में तत्व। सूचियों को प्राथमिकता कतार (ढेर (डेटा संरचना) | न्यूनतम-ढेर) में उनके पहले तत्व द्वारा कुंजीबद्ध करके इसे सुधारा जा सकता है:

• मिनी-हीप बनाएं h की k कुंजी के रूप में पहले तत्व का उपयोग करते हुए सूचीबद्ध करता है।
• जबकि कोई भी सूची खाली नहीं है:
  • होने देना i = find-min(h).
  • सूची का पहला तत्व आउटपुट करें i और इसे इसकी सूची से हटा दें।
  • पुनः ढेर करें h.

आउटपुट (फाइंड-मिन) होने के लिए अगले सबसे छोटे तत्व की खोज करना एवं हीप ऑर्डर को पुनर्स्थापित करना अब में किया जा सकता है O(log k) समय (अधिक विशेष रूप से, 2⌊log k⌋ तुलना), एवं पूरी समस्या को हल किया जा सकता है O(n log k) समय (लगभग 2n⌊log k⌋ तुलना)।

समस्या के लिए एक तीसरा एल्गोरिथम एक विभाजन एवं जीत एल्गोरिथम समाधान है जो बाइनरी मर्ज एल्गोरिथम पर बनाता है:

• अगर k = 1, एकल इनपुट सूची का उत्पादन करें।
• अगर k = 2, बाइनरी मर्ज करें।
• अन्यथा, पुनरावर्ती रूप से पहले मर्ज करें ⌊k/2⌋ सूचियाँ और अंतिम ⌈k/2⌉ सूचियाँ, फिर बाइनरी इन्हें मर्ज करें।

जब इस एल्गोरिथम की इनपुट सूचियों को लंबाई के अनुसार क्रमबद्ध किया जाता है, तो सबसे पहले, इसके लिए इससे कम की आवश्यकता होती है n⌈log k⌉ तुलना, यानी ढेर-आधारित एल्गोरिथम द्वारा उपयोग की जाने वाली संख्या के आधे से भी कम; व्यवहार में, यह ढेर-आधारित एल्गोरिथम जितना तेज़ या धीमा हो सकता है।

समानांतर विलय

बाइनरी मर्ज एल्गोरिथम का एक कार्य समानता संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली (कॉर्मेन एट अल।). यह दो क्रमबद्ध सरणियों पर काम करता है A एवं B एवं क्रमबद्ध आउटपुट को सारणी में लिखता है C. अंकन A[i...j] का हिस्सा दर्शाता है A इंडेक्स से i द्वारा j, अनन्य।

एल्गोरिदम मर्ज (ए[आई...जे], बी[के...ℓ], सी[पी...क्यू]) है
    इनपुट ए, बी, सी: सारणी
           i, j, k, ℓ, p, q : सूचकांक

    चलो एम = जे - मैं,
        एन = ℓ - के

    अगर एम <एन तो
        स्वैप ए एवं बी  // सुनिश्चित करें कि ए बड़ा सारणी है: i, j अभी भी A से संबंधित है; k, ℓ से B
        एम एवं एन स्वैप करें

    अगर एम ≤ 0 तो
        रिटर्न // बेस केस, मर्ज करने के लिए कुछ नहीं

    चलो आर = ⌊(i + j)/2⌋
    चलो एस = बाइनरी-सर्च (ए [आर], बी [के ... ℓ])
    माना टी = पी + (आर - आई) + (एस - के)
    सी [टी] = ए [आर]

    समानांतर करते हैं
        मर्ज (ए[आईआर...आर], बी[के...एस], सी[पी...टी])
        विलय (ए [आर + 1 ... जे], बी [एस ... ℓ], सी [टी + 1 ... क्यू])

एल्गोरिथ्म या तो विभाजित करके संचालित होता है A या B, जो भी बड़ा हो, (लगभग) बराबर हिस्सों में। इसके बाद यह दूसरे सारणी को पहले के मध्य बिंदु से छोटे मान वाले भाग में एवं बड़े या समान मान वाले भाग में विभाजित करता है। (द्विआधारी खोज उपनेमका सूचकांक को अंदर लौटाता है B कहाँ A[r] होगा, अगर यह अंदर होता B; कि यह हमेशा के बीच एक संख्या है k एवं ℓ।) अंत में, हिस्सों की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम जीतते हैं, एवं चूंकि रिकर्सिव कॉल एक दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां रिकर्सन बेस केस के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है समांतर एल्गोरिदम का विश्लेषण # एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन n एलिमेंट्स, यानी इसके सीरियल वर्जन का रनिंग टाइम है O(n). यह तब से इष्टतम है n तत्वों को कॉपी करने की आवश्यकता है C. समांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए # एल्गोरिदम का अवलोकन, पुनरावृत्ति संबंध प्राप्त करना आवश्यक है। चूंकि विलय की दो रिकर्सिव कॉल समानांतर में हैं, केवल दो कॉलों के महंगे होने पर विचार करने की आवश्यकता है। सबसे खराब स्थिति में, एक पुनरावर्ती कॉल में तत्वों की अधिकतम संख्या अधिकतम होती है ${\textstyle {\frac {3}{4}}n}$ चूंकि अधिक तत्वों वाला सारणी आधे में पूरी तरह से विभाजित है। जोड़ना $\Theta \left(\log(n)\right)$ बाइनरी सर्च की लागत, हम इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं:

$T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$ समाधान है $T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)$, जिसका अर्थ है कि एक आदर्श मशीन पर असीमित संख्या में प्रोसेसर के साथ इतना समय लगता है।

नोट: रूटीन छँटाई एल्गोरिथ्म नहीं है # स्थिरता: यदि समान आइटम विभाजित करके अलग किए जाते हैं A एवं B, वे इसमें इंटरलीव हो जाएंगे C; अदला-बदली भी A एवं B ऑर्डर को नष्ट कर देगा, यदि दोनों इनपुट सरणियों के बीच समान आइटम फैले हुए हैं। परिणामस्वरूप, जब छँटाई के लिए उपयोग किया जाता है, तो यह एल्गोरिथम एक ऐसा क्रम उत्पन्न करता है जो स्थिर नहीं होता है।

दो सूचियों का समानांतर विलय

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

मौजूदा समानांतर एल्गोरिदम या तो बिटोनिक सॉर्टर या सम-विषम मर्ज सॉर्ट के मर्ज भाग के संशोधनों पर आधारित हैं। 2018 में, सैतोह एम। एट अल। एमएमएस पेश किया FPGAs के लिए, जो एक बहु-चक्र फीडबैक डेटापथ को हटाने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अलावा 2018 में, Papaphilippou P. et al। FLiMS पेश किया जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग एवं प्रदर्शन में सुधार किया $\log _{2}(P)+1$ के पाइपलाइन चरण P/2 की समानता के साथ विलय करने के लिए इकाइयों की तुलना एवं अदला-बदली करें P एफपीजीए चक्र प्रति तत्व।

भाषा समर्थन

कुछ कंप्यूटर भाषाएँ सॉर्ट किए गए संग्रह (सार डेटा प्रकार) को मर्ज करने के लिए अंतर्निहित या लाइब्रेरी समर्थन प्रदान करती हैं।

सी ++

सी ++ की मानक टेम्पलेट लाइब्रेरी में फ़ंक्शन है std::merge, जो पुनरावर्तकों की दो क्रमबद्ध श्रेणियों को मिलाता है, एवं std::inplace_merge, जो लगातार दो क्रमबद्ध श्रेणियों को इन-प्लेस मर्ज करता है। इसके साथ में std::list (लिंक की गई सूची) वर्ग का अपना है merge विधि जो दूसरी सूची को अपने आप में विलीन कर देती है। विलय किए गए तत्वों के प्रकार को इससे कम का समर्थन करना चाहिए (<) ऑपरेटर, या इसे एक कस्टम तुलनित्र प्रदान किया जाना चाहिए।

सी ++ 17 अलग-अलग निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समांतर, एवं समांतर-अनुक्रमित।

पायथन

पायथन (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी (2.6 के बाद से) में भी a merge में कार्य करता है heapq मॉड्यूल, जो कई क्रमबद्ध पुनरावृत्तियों को लेता है, एवं उन्हें एक एकल पुनरावर्तक में मिला देता है।

यह भी देखें

• विलय (संशोधन नियंत्रण)
• जुड़ें (संबंधपरक बीजगणित)
• जुड़ें (एसक्यूएल)
• जुड़ें (यूनिक्स)

अग्रिम पठन

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.

बाहरी संबंध

• High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub