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

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

आवेदन

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

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

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

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

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

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

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

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B
        return C    

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

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

के-वे विलीनीकरण

Main article: k-वे विलय एल्गोरिथम

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

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

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

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

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

आउटपुट होने के लिए आगामी सबसे अल्प तत्व का शो करना एवं हीप ऑर्डर को पुनर्स्थापित करना O(log k) में किया जा सकता है, एवं पूर्ण समस्या का समाधान किया जा सकता है।

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

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

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

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

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

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])

merge(A[r+1...j], B[s...ℓ], C[t+1...q])

एल्गोरिथ्म या तो विभाजित करके संचालित होता है A या B, जो भी बड़ा हो, (लगभग) समान भागो में इसके पश्चात यह दूसरे सरणी को प्रथम के मध्य बिंदु से अल्प मान वाले भाग में एवं बड़े या समान मान वाले भाग में विभाजित करता है। अंत में, भागो की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम विजयी होते हैं, एवं चूंकि रिकर्सिव कॉल दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां पुनरावर्तन आधार विषय के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है। समांतर एल्गोरिदम का विश्लेषण एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन 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) निर्देशों के साथ किया जा सकता है।

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

भाषा समर्थन

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

C ++

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

C ++ 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