मर्ज एल्गोरिथम: Difference between revisions

Revision as of 16:11, 17 May 2023

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

आवेदन

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

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

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

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

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

दो सूचियों को मर्ज करना

दो क्रमबद्ध सूचियों को एक में विलय करना रैखिक समय एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित स्यूडोकोड एक एल्गोरिथम प्रदर्शित करता है जो इनपुट सूचियों (या तो लिंक्ड सूचियों या सारणी डेटा संरचना) को मर्ज करता है $A$ एवं $B$ एक नई सूची में $C$ .^[1]^[2]^: 104 कार्यक्रम head सूची का पहला तत्व उत्पन्न करता है; किसी तत्व को छोड़ने का मतलब है कि इसे सूची से हटाना, आमतौर पर पॉइंटर या इंडेक्स को बढ़ाकर।

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

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

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

    वापसी सी

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

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

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

$k$ -वे मर्जिंग बाइनरी मर्जिंग को मनमाना संख्या में सामान्यीकृत करता है $k$ क्रमबद्ध इनपुट सूचियों की। के आवेदन $k$ -वे मर्जिंग विभिन्न सॉर्टिंग एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य सॉर्टिंग भी सम्मिलित है^[5] एवं एक बाहरी छँटाई एल्गोरिथ्म जो इसके इनपुट को विभाजित करता है $k = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/M − 1$ ब्लॉक जो मेमोरी में फिट होते हैं, इन्हें एक-एक करके सॉर्ट करते हैं, फिर इन ब्लॉक्स को मर्ज कर देते हैं।^[2]^{: 119–120}

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

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

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

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

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

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

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

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

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

बाइनरी मर्ज एल्गोरिथम का एक कार्य समानता संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली (कॉर्मेन एट अल।^[7]^: 800). यह दो क्रमबद्ध सरणियों पर काम करता है $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$ एवं $ℓ$ ।) अंत में, हिस्सों की प्रत्येक जोड़ी विलय कर दी जाती है एवं एल्गोरिदम जीतते हैं, एवं चूंकि रिकर्सिव कॉल एक दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां रिकर्सन बेस केस के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करने के लिए दिखाया गया है ^[8] समांतर एल्गोरिदम का विश्लेषण # एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन $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)$ , जिसका अर्थ है कि एक आदर्श मशीन पर असीमित संख्या में प्रोसेसर के साथ इतना समय लगता है।^[7]^{: 801–802}

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

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

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

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

भाषा समर्थन

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

सी ++

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

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

पायथन

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

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.
↑ ^2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.
↑ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.
↑ Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.
↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-आरी सॉर्ट (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.
↑ ^7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
↑ Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal
↑ ^9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271.
↑ Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM): 197–204. doi:10.1109/FCCM.2018.00038.
↑ "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.
↑ "heapq — Heap queue algorithm — Python 3.10.1 documentation".

अग्रिम पठन

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

[skiena-1] 1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथ्म डिजाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.

[toolbox-2] 2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.

[3] Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.

[4] Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलना द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.

[Chandramouli-5] Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.

[greene-6] 6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-आरी सॉर्ट (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.

[clrs-7] 7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[vjd-8] Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal

[flimsj-9] 9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271.

[10] Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "फीडबैक डेटापथ के बिना एक उच्च-प्रदर्शन और लागत प्रभावी हार्डवेयर मर्ज सॉर्टर". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM): 197–204. doi:10.1109/FCCM.2018.00038.

[11] "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.

[12] "heapq — Heap queue algorithm — Python 3.10.1 documentation".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 5: / Line 5: @@
 [[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|मर्ज सॉर्ट के लिए एक उदाहरण]]मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिथ्म में महत्वपूर्ण भूमिका निभाता है, तुलना-आधारित सॉर्टिंग एल्गोरिदम वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथम में दो चरण होते हैं।
-# पुनरावर्तन (कंप्यूटर विज्ञान) सूची को (मोटे तौर पर) समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल एक तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट के मामले में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें आकार 1 का। परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
+# पुनरावर्तन (कंप्यूटर विज्ञान) सूची को समान लंबाई की उपसूचियों में विभाजित करता है, जब तक कि प्रत्येक उपसूची में केवल तत्व न हो, या पुनरावृत्त (नीचे ऊपर) मर्ज सॉर्ट की स्थिति में, n उप-सूचियों के रूप में n तत्वों की सूची पर विचार करें। 1 आकार के परिभाषा के अनुसार, एकल तत्व वाली सूची को क्रमबद्ध किया जाता है।
-# जब तक एकल सूची में सभी तत्व शामिल नहीं हो जाते, तब तक एक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को मर्ज करें। एकल सूची क्रमबद्ध सूची है।
+# जब तक एकल सूची में सभी तत्व सम्मिलित नहीं हो जाते, तब तक नई क्रमबद्ध सबलिस्ट बनाने के लिए बार-बार सब्लिस्ट्स को विलय करें। एकल सूची क्रमबद्ध सूची है।
 मर्ज सॉर्ट एल्गोरिथम में मर्ज एल्गोरिथ्म का बार-बार उपयोग किया जाता है।
-उदाहरण में मर्ज सॉर्ट का उदाहरण दिया गया है। यह 7 पूर्णांकों की एक अवर्गीकृत सरणी से शुरू होता है। सरणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है एवं इसे क्रमबद्ध किया जाता है। तब छांटे गए विभाजनों को बड़ा, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 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}} सूची का पहला तत्व उत्पन्न करता है; किसी तत्व को छोड़ने का मतलब है कि इसे सूची से हटाना, आमतौर पर पॉइंटर या इंडेक्स को बढ़ाकर।
+दो क्रमबद्ध सूचियों को एक में विलय करना [[रैखिक समय]] एवं रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित [[स्यूडोकोड]] एक एल्गोरिथम प्रदर्शित करता है जो इनपुट सूचियों (या तो लिंक्ड सूचियों या [[सरणी डेटा संरचना|सारणी डेटा संरचना]]) को मर्ज करता है {{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}} सूची का पहला तत्व उत्पन्न करता है; किसी तत्व को छोड़ने का मतलब है कि इसे सूची से हटाना, आमतौर पर पॉइंटर या इंडेक्स को बढ़ाकर।
   एल्गोरिथम मर्ज (ए, बी) है
@@ Line 41: / Line 41: @@
 जब इनपुट लिंक्ड सूचियाँ हैं, तो इस एल्गोरिथम को केवल कार्य स्थान की एक स्थिर मात्रा का उपयोग करने के लिए लागू किया जा सकता है; सूचियों के नोड्स में पॉइंटर्स को बहीखाता पद्धति के लिए एवं अंतिम मर्ज की गई सूची के निर्माण के लिए पुन: उपयोग किया जा सकता है।
-मर्ज सॉर्ट एल्गोरिथम में, यह सबरूटीन आमतौर पर दो उप-सरणियों को मर्ज करने के लिए उपयोग किया जाता है {{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|Merge sort|Variants}} चर्चा के लिए।
+मर्ज सॉर्ट एल्गोरिथम में, यह सबरूटीन आमतौर पर दो उप-सरणियों को मर्ज करने के लिए उपयोग किया जाता है {{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|Merge sort|Variants}} चर्चा के लिए।
 == के-वे मर्जिंग ==
 {{Main|K-way merge algorithm}}
-{{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}}-वे मर्जिंग बाइनरी मर्जिंग को मनमाना संख्या में सामान्यीकृत करता है {{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}} प्रत्येक बार न्यूनतम तत्व चुनने के लिए सूचीबद्ध करता है, एवं इस लूप को तब तक दोहराता है जब तक कि सभी सूचियां खाली न हो जाएं:
@@ Line 86: / Line 86: @@
 == समानांतर विलय ==
-बाइनरी मर्ज एल्गोरिथम का एक [[कार्य समानता]] संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली (कॉर्मेन एट अल।<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}}, अनन्य।
+बाइनरी मर्ज एल्गोरिथम का एक [[कार्य समानता]] संस्करण मर्ज सॉर्ट # समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिथम को एक फोर्क-जॉइन मॉडल में प्रदर्शित करता है। समानांतर विभाजन एवं जीत शैली (कॉर्मेन एट अल।<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 : सूचकांक
@@ Line 96: / Line 96: @@
       अगर एम <एन तो
-          स्वैप ए एवं बी '' // सुनिश्चित करें कि ए बड़ा सरणी है: i, j अभी भी A से संबंधित है; k, ℓ से B''
+          स्वैप ए एवं बी '' // सुनिश्चित करें कि ए बड़ा सारणी है: i, j अभी भी A से संबंधित है; k, ℓ से B''
           एम एवं एन स्वैप करें
@@ Line 111: / Line 111: @@
           विलय (ए [आर + 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|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> बाइनरी सर्च की लागत, हम इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं:
+समांतर एल्गोरिदम का विश्लेषण # एल्गोरिदम द्वारा कुल मिलाकर दो सारणी के लिए किया गया अवलोकन {{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>

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

मर्ज एल्गोरिथम: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:11, 17 May 2023

Contents

आवेदन

दो सूचियों को मर्ज करना

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

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

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

भाषा समर्थन

सी ++

पायथन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मर्ज एल्गोरिथम: Difference between revisions

Revision as of 16:11, 17 May 2023

आवेदन

दो सूचियों को मर्ज करना

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

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

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

भाषा समर्थन

सी ++

पायथन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories