View source for मर्ज एल्गोरिथम

{{Short description|Algorithm that combines multiple sorted lists into one}}
मर्ज [[कलन विधि]] एल्गोरिदम का परिवार है जो इनपुट के रूप में कई [[छँटाई एल्गोरिथ्म]] सूचियों को लेता है एवं आउटपुट के रूप में एकल सूची का उत्पादन करता है, जिसमें इनपुट सूची के सभी तत्व क्रमबद्ध क्रम में होते हैं। इन एल्गोरिदम का उपयोग विभिन्न सॉर्टिंग एल्गोरिदम में [[सबरूटीन]] के रूप में किया जाता है।

== आवेदन ==
[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|मर्ज सॉर्ट के लिए एक उदाहरण]]मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में महत्वपूर्ण भूमिका निभाता है, तुलना-आधारित सॉर्टिंग एल्गोरिदम वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं।

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

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

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

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

दो क्रमबद्ध सूचियों को विलय करना [[रैखिक समय]] एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित [[स्यूडोकोड]] एल्गोरिथम प्रदर्शित करता है, जो इनपुट सूचियों (या तो लिंक्ड सूचियों या [[सरणी डेटा संरचना|सारणी डेटा संरचना]]) को विलय करता है, {{mvar|A}} एवं {{mvar|B}} नई सूची {{mvar|C}} में<ref name="skiena">{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title=एल्गोरिथ्म डिजाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-4 |page=123}}</ref>{{r|toolbox}}{{rp|104}} कार्यक्रम {{mono|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

    

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

प्रसूची वरण एल्गोरिथम में, यह सबरूटीन सामान्यतः दो उप-सरणियों को विलय करने के लिए उपयोग किया जाता है {{mono|A[lo..mid]}}, {{mono|A[mid+1..hi]}} एकल सारणी का यह उप-सरणियों {{mono|A}} को अस्थायी सारणी में कॉपी करके, ऊपर विलय एल्गोरिथ्म को प्रारम्भ करके किया जा सकता है।{{r|skiena}} अस्थायी सारणी के आवंटन से बचा जा सकता है, किन्तु गति एवं प्रोग्रामिंग सरलता के मूल्य पर विभिन्न स्थान में विलय एल्गोरिदम प्रस्तुत किए गए हैं,<ref>{{cite journal |last1=Katajainen |first1=Jyrki |first2=Tomi |last2=Pasanen |first3=Jukka |last3=Teuhola |title=प्रैक्टिकल इन-प्लेस मर्जसॉर्ट|journal=Nordic J. Computing |volume=3 |issue=1 |year=1996 |pages=27–40 |citeseerx=10.1.1.22.8523}}</ref> कभी-कभी उत्पादन करने के लिए रैखिक-समयबद्धता का त्याग करना {{math|''O''(''n'' log ''n'')}} कलन विधि;<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| title = सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> देखना {{slink|प्रसूची वरण|रूपांतर}} विषय के लिए होता है।

== के-वे विलीनीकरण ==
{{Main|k-वे विलय एल्गोरिथम}}
{{mvar|k}}-वे विलीनीकरण बाइनरी विलीनीकरण को मनमाना संख्या में सामान्यीकृत करता है, {{mvar|k}} क्रमबद्ध इनपुट सूचियों के आवेदन {{mvar|k}}-वे विलीनीकरण विभिन्न वर्गीकृत एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य वर्गीकृत भी सम्मिलित है<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref> एवं [[बाहरी छँटाई|बाहरी वर्गीकृत]] एल्गोरिथ्म जो इसके इनपुट  {{math|''k'' {{=}} {{sfrac|1|''M''}} − 1}} को विभाजित करता है, इन्हें चयनित करते हैं, इन ब्लॉक्स को विलय कर देते हैं।{{r|toolbox}}{{rp|119–120}}

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

<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >{{framebox|blue}}
* इनपुट: की सूची {{mvar|k}} सूचियाँ होती है।
* जबकि कोई भी सूची रिक्त नहीं है।
** न्यूनतम प्रथम तत्व वाले का शोधन करने के लिए सूचियों पर लूप करें।
** न्यूनतम तत्व को आउटपुट करें और इसे उसकी सूची से विस्थापित कर दें।
{{frame-footer}}
</div>

सबसे उत्तम, सबसे निकृष्ट एवं औसत विषय {{math|(''k''−1)(''n''−{{sfrac|''k''|2}})}} यह एल्गोरिथ्म प्रदर्शन करता है, तत्वों की तुलना स्वयं कार्य को करने के लिए की जाती है तो कुल मिलाकर {{mvar|n}} सूचियों में तत्व<ref name="greene">{{cite conference |last=Greene |first=William A. |year=1993 |title=के-वे मर्जिंग और के-आरी सॉर्ट|conference=Proc. 31-st Annual ACM Southeast Conf |pages=127–135 |url=http://www.cs.uno.edu/people/faculty/bill/k-way-merge-n-sort-ACM-SE-Regl-1993.pdf}}</ref> को [[प्राथमिकता कतार]] [[ढेर (डेटा संरचना)|(डेटा संरचना)]] में उनके प्रथम तत्व द्वारा कुंजीबद्ध करके इसे सही किया जा सकता है।

<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
{{framebox|blue}}
* कुंजी के रूप {{mvar|में}}प्रथम {{mvar|k}}  तत्व का उपयोग करके k सूचियों का न्यूनतम-सूचीबद्ध h बनाएँ।
* जबकि कोई भी सूची रिक्त नहीं है।
** होने देना {{math|''i'' {{=}} find-min(''h'')}}.
** सूची का प्रथम तत्व आउटपुट करें {{mvar|i}} एवं इसे इसको सूची से विस्थापित कर दें।
** पुनः h सूचीबद्ध {{mvar|करें}}.
{{frame-footer}}
</div>

आउटपुट होने के लिए आगामी सबसे अल्प तत्व का शो करना एवं हीप ऑर्डर को पुनर्स्थापित करना {{math|''O''(log ''k'')}} में किया जा सकता है,{{r|greene}} एवं पूर्ण  समस्या का समाधान किया जा सकता है।{{r|greene}}<ref name="toolbox">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox |date=2008 |publisher=Springer |isbn=978-3-540-77978-0 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/}}</ref>{{rp|119–120}}

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

<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
{{framebox|blue}}
* अगर {{math|''k'' {{=}} 1}}, एकल इनपुट सूची का उत्पादन करें।
* अगर {{math|''k'' {{=}} 2}}, बाइनरी मर्ज करें।
* अन्यथा, पुनरावर्ती रूप से पहले मर्ज करें {{math|⌊''k''/2⌋}} सूचियाँ और अंतिम {{math|⌈''k''/2⌉}} सूचियाँ, फिर बाइनरी इन्हें मर्ज करें।
{{frame-footer}}
</div>

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

== समानांतर विलय ==
बाइनरी मर्ज एल्गोरिथम का एक [[कार्य समानता]] संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली (कॉर्मेन एट अल।<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}}). यह दो क्रमबद्ध सरणियों पर काम करता है {{mvar|A}} एवं {{mvar|B}} एवं क्रमबद्ध आउटपुट को सारणी में लिखता है {{mvar|C}}. अंकन {{mono|A[i...j]}} का हिस्सा दर्शाता है {{mvar|A}} इंडेक्स से {{mvar|i}} द्वारा {{mvar|j}}, अनन्य।

 एल्गोरिदम मर्ज (ए[आई...जे], बी[के...ℓ], सी[पी...क्यू]) है
     इनपुट ए, बी, सी: सारणी
            i, j, k, ℓ, p, q : सूचकांक
 
     चलो एम = जे - मैं,
         एन = ℓ - के
 
     अगर एम <एन तो
         स्वैप ए एवं बी '' // सुनिश्चित करें कि ए बड़ा सारणी है: i, j अभी भी A से संबंधित है; k, ℓ से B''
         एम एवं एन स्वैप करें
 
     अगर एम ≤ 0 तो
         रिटर्न ''// बेस केस, मर्ज करने के लिए कुछ नहीं''
 
     चलो आर = ⌊(i + j)/2⌋
     चलो एस = बाइनरी-सर्च (ए [आर], बी [के ... ℓ])
     माना टी = पी + (आर - आई) + (एस - के)
     सी [टी] = ए [आर]
 
     समानांतर करते हैं
         मर्ज (ए[आईआर...आर], बी[के...एस], सी[पी...टी])
         विलय (ए [आर + 1 ... जे], बी [एस ... ℓ], सी [टी + 1 ... क्यू])

एल्गोरिथ्म या तो विभाजित करके संचालित होता है {{mvar|A}} या {{mvar|B}}, जो भी बड़ा हो, (लगभग) बराबर हिस्सों में। इसके बाद यह दूसरे सारणी को पहले के मध्य बिंदु से छोटे मान वाले भाग में एवं बड़े या समान मान वाले भाग में विभाजित करता है। ([[द्विआधारी खोज]] उपनेमका सूचकांक को अंदर लौटाता है {{mvar|B}} कहाँ {{math|''A''[''r'']}} होगा, अगर यह अंदर होता {{mvar|B}}; कि यह हमेशा के बीच एक संख्या है {{mvar|k}} एवं {{mvar|ℓ}}।) अंत में, हिस्सों की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम जीतते हैं, एवं चूंकि रिकर्सिव कॉल एक दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां रिकर्सन बेस केस के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है <ref name="vjd">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>
समांतर एल्गोरिदम का विश्लेषण # एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन {{mvar|n}} एलिमेंट्स, यानी इसके सीरियल वर्जन का रनिंग टाइम है {{math|''O''(''n'')}}. यह तब से इष्टतम है {{mvar|n}} तत्वों को कॉपी करने की आवश्यकता है {{mvar|C}}. समांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए # एल्गोरिदम का अवलोकन, [[पुनरावृत्ति संबंध]] प्राप्त करना आवश्यक है। चूंकि विलय की दो रिकर्सिव कॉल समानांतर में हैं, केवल दो कॉलों के महंगे होने पर विचार करने की आवश्यकता है। सबसे खराब स्थिति में, एक पुनरावर्ती कॉल में तत्वों की अधिकतम संख्या अधिकतम होती है <math display="inline">\frac 3 4 n</math> चूंकि अधिक तत्वों वाला सारणी आधे में पूरी तरह से विभाजित है। जोड़ना <math>\Theta\left( \log(n)\right)</math> बाइनरी सर्च की लागत, हम इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं:

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

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

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

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

उपस्थिता समानांतर एल्गोरिदम या तो [[बिटोनिक सॉर्टर]] या [[सम-विषम मर्ज सॉर्ट]] के मर्ज भाग के संशोधनों पर आधारित हैं।<ref name="flimsj">{{cite journal |last1=Papaphilippou |first1=Philippos |last2=Luk |first2=Wayne |last3=Brooks |first3=Chris |title=FLiMS: a Fast Lightweight 2-way Merger for Sorting |journal=IEEE Transactions on Computers |date=2022 |pages=1–12 |doi=10.1109/TC.2022.3146509|hdl=10044/1/95271 |hdl-access=free }}</ref> 2018 में, सैतोह एम। एट अल। एमएमएस पेश किया <ref>{{cite journal |last1=Saitoh |first1=Makoto |last2=Elsayed |first2=Elsayed A. |last3=Chu |first3=Thiem Van |last4=Mashimo |first4=Susumu |last5=Kise |first5=Kenji |title=फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) |date=April 2018 |pages=197–204 |doi=10.1109/FCCM.2018.00038}}</ref> FPGAs के लिए, जो एक बहु-चक्र फीडबैक डेटापथ को हटाने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अलावा 2018 में, Papaphilippou P. et al। FLiMS पेश किया <ref name="flimsj" />जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग एवं प्रदर्शन में सुधार किया <math>\log_2(P)+1</math> के पाइपलाइन चरण {{math|''P/2''}} की समानता के साथ विलय करने के लिए इकाइयों की तुलना एवं अदला-बदली करें {{math|''P''}} एफपीजीए चक्र प्रति तत्व।

== भाषा समर्थन ==

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

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

सी ++ 17 अलग-अलग निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समांतर, एवं समांतर-अनुक्रमित।<ref>{{cite web| url=http://en.cppreference.com/w/cpp/algorithm/merge| title=std:merge| publisher=cppreference.com| date=2018-01-08| access-date=2018-04-28}}</ref>


=== पायथन ===
पायथन (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी (2.6 के बाद से) में भी a {{mono|merge}} में कार्य करता है {{mono|heapq}} मॉड्यूल, जो कई क्रमबद्ध पुनरावृत्तियों को लेता है, एवं उन्हें एक एकल पुनरावर्तक में मिला देता है।<ref>{{cite web| url = https://docs.python.org/library/heapq.html#heapq.merge| title = heapq — Heap queue algorithm — Python 3.10.1 documentation}}</ref>


== यह भी देखें ==
* [[विलय (संशोधन नियंत्रण)]]
* जुड़ें (संबंधपरक बीजगणित)
* जुड़ें (एसक्यूएल)
* जुड़ें (यूनिक्स)

== संदर्भ ==
{{Reflist}}


== अग्रिम पठन ==
* [[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.&nbsp;197–207.


==बाहरी संबंध==
*[https://duvanenko.tech.blog/2018/05/23/faster-sorting-in-c/ High Performance Implementation] of Parallel and Serial Merge in [[C Sharp (programming language)|C#]] with source in [https://github.com/DragonSpit/HPCsharp/ GitHub] and in [[C++]] [https://github.com/DragonSpit/ParallelAlgorithms GitHub]

{{sorting}}

{{DEFAULTSORT:Merge Algorithm}}[[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: छँटाई एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 13/05/2023]]