मर्ज सॉर्ट: एल्गोरिथम, फायदे और विशेषताएं

2024 लेखक: Angel Austin | [email protected]. अंतिम बार संशोधित: 2024-02-02 15:35

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

एल्गोरिदम का सिद्धांत और उपयोग

मर्ज सॉर्ट पद्धति का उपयोग सरणियों, सूचियों, धाराओं जैसे तत्वों तक पहुंच का आदेश देने वाली संरचनाओं को छांटने की समस्याओं में किया जाता है।

प्रसंस्करण के दौरान, प्रारंभिक डेटा ब्लॉक को छोटे घटकों में विभाजित किया जाता है, एक तत्व तक, जो वास्तव में पहले से ही एक क्रमबद्ध सूची है। फिर इसे सही क्रम में फिर से जोड़ा जाता है।

एक निश्चित लंबाई की एक सरणी को सॉर्ट करने के लिए उसी आकार के एक अतिरिक्त मेमोरी क्षेत्र की आवश्यकता होती है, जिसमें सॉर्ट किए गए सरणी को भागों में एकत्र किया जाता है।

विधि का उपयोग किसी भी तुलनीय डेटा प्रकार, जैसे संख्या या स्ट्रिंग को ऑर्डर करने के लिए किया जा सकता है।

मर्ज सॉर्ट किया गयाभूखंड

एल्गोरिदम को समझने के लिए, आइए इसका विश्लेषण अंत से शुरू करें - सॉर्ट किए गए ब्लॉकों को मर्ज करने के तंत्र से।

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

प्राथमिक उदाहरण: दोनों सरणियों में प्रत्येक में एक तत्व होता है।

int arr1={31}; int arr2={18};

उन्हें मर्ज करने के लिए, आपको पहली सरणी का शून्य तत्व (यह मत भूलना कि नंबरिंग शून्य से शुरू होता है) और दूसरी सरणी का शून्य तत्व लेना होगा। ये क्रमशः 31 और 18 हैं। छँटाई की स्थिति के अनुसार, संख्या 18 सबसे पहले आनी चाहिए, क्योंकि यह कम है। बस संख्याओं को सही क्रम में रखें:


int परिणाम={18, 31};

आइए अधिक जटिल उदाहरण देखें, जहां प्रत्येक सरणी में कई तत्व होते हैं:


int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};

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


इंट इंडेक्स1=0; इंट इंडेक्स2=0;

आइए पूरी मर्जिंग प्रक्रिया को चरण दर चरण लिखें:

अरे arr1 से index1 के साथ एलिमेंट लें, और array arr2 से index2 वाले एलिमेंट को लें।
तुलना करें, उनमें से सबसे छोटा चुनें और डालेंपरिणामी सरणी।
छोटे तत्व के वर्तमान सूचकांक को 1 से बढ़ाएँ।
पहले चरण से जारी रखें।






पहली कक्षा में ऐसी दिखेगी स्थिति:


सूचकांक1=0; अनुक्रमणिका2=0; एआर 1 [0]=2; एआर 2 [0]=5; arr1[0] < arr2[0]; अनुक्रमणिका1++; परिणाम [0]=एआर 1 [0]; // परिणाम=[2]

दूसरे मोड़ पर:


सूचकांक1=1; अनुक्रमणिका2=0; एआर 1 [1]=17; एआर 2 [0]=5; arr1[1] > arr2[0]; अनुक्रमणिका2++; परिणाम [1]=गिरफ्तारी 2 [0]; // परिणाम=[2, 5]

तीसरा:


सूचकांक1=1; अनुक्रमणिका 2=1; एआर 1 [1]=17; एआर 2 [1]=6; arr1[1] > arr2[1]; अनुक्रमणिका2++; परिणाम [2]=एआर 2 [1]; // परिणाम=[2, 5, 6]

और इसी तरह, जब तक परिणाम पूरी तरह से क्रमबद्ध सरणी न हो: {2, 5, 6, 17, 21, 19, 30, 45}।
यदि अलग-अलग लंबाई वाले सरणियों को मिला दिया जाए तो कुछ कठिनाइयाँ उत्पन्न हो सकती हैं। क्या होगा यदि वर्तमान अनुक्रमणिका में से एक अंतिम तत्व तक पहुंच गया है, और दूसरी सरणी में अभी भी सदस्य शेष हैं?


int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 स्टेप इंडेक्स 1=0, इंडेक्स 2=0; 1 2 परिणाम={1, 2}; // 3 स्टेप इंडेक्स 1=1, इंडेक्स 2=1; 4 < 5 परिणाम={1, 2, 4}; //4 चरण अनुक्रमणिका1=2, अनुक्रमणिका2=1 ??

इंडेक्स1 वेरिएबल मान 2 पर पहुंच गया है, लेकिन arr1 सरणी में उस इंडेक्स के साथ कोई तत्व नहीं है। यहां सब कुछ सरल है: बस दूसरी सरणी के शेष तत्वों को उनके क्रम को बनाए रखते हुए परिणामी में स्थानांतरित करें।


परिणाम={1, 2, 4, 5, 6, 7, 9};

यह स्थिति हमें आवश्यकता की ओर इशारा करती हैमर्ज किए जा रहे सरणी की लंबाई के साथ वर्तमान चेक इंडेक्स का मिलान करें।
विभिन्न लंबाई के क्रमबद्ध अनुक्रमों (ए और बी) के लिए योजना मर्ज करें:

यदि दोनों अनुक्रमों की लंबाई 0 से अधिक है, तो A[0] और B[0] की तुलना करें और छोटे वाले को बफर में ले जाएं।
यदि किसी एक क्रम की लंबाई 0 है, तो दूसरे क्रम के शेष तत्वों को लें और उनके क्रम को बदले बिना बफ़र के अंत में जाएँ।


दूसरे चरण का क्रियान्वयन
जावा में दो क्रमबद्ध सरणियों को जोड़ने का एक उदाहरण नीचे दिया गया है।


int a1=नया int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; इंट ए 2=नया इंट {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=नया int[a1.length + a2.length]; इंट आई=0, जे=0; के लिए (int k=0; k a1.length-1) { int a=a2[j]; ए 3 [के]=ए; जे++; } और अगर (j > a2.length-1) {int a=a1; ए 3 [के]=ए; मैं++; } और अगर (a1 < a2[j]) {int a=a1; ए 3 [के]=ए; मैं++; } और { इंट बी=ए 2 [जे]; ए 3 [के]=बी; जे++; } }

यहाँ:

a1 और a2 मर्ज किए जाने वाले मूल सॉर्ट किए गए सरणियाँ हैं;
a3 - अंतिम सरणी;
i और j सरणियों a1 और a2 के लिए वर्तमान तत्वों के सूचकांक हैं।

पहली और दूसरी अगर स्थितियां सुनिश्चित करती हैं कि अनुक्रमणिका सरणी के आकार से आगे नहीं जाती है। क्रमशः तीसरे और चौथे कंडीशन ब्लॉक्स को छोटे एलिमेंट के परिणामी ऐरे में ले जाया जाता है।






फूट डालो और जीतो
तो, हमने सॉर्ट करना सीख लिया हैमूल्यों का संग्रह। यह कहा जा सकता है कि मर्ज सॉर्ट एल्गोरिथम का दूसरा भाग - मर्ज ही - पहले ही सॉर्ट किया जा चुका है।
हालाँकि, आपको अभी भी यह समझने की आवश्यकता है कि संख्याओं के मूल अवर्गीकृत सरणी से कई क्रमबद्ध संख्याएँ कैसे प्राप्त की जा सकती हैं जिन्हें मर्ज किया जा सकता है।
आइए एल्गोरिथम के पहले चरण पर विचार करें और सरणियों को अलग करना सीखें।
यह मुश्किल नहीं है - मूल्यों की मूल सूची को आधे में विभाजित किया जाता है, फिर प्रत्येक भाग को भी विभाजित किया जाता है, और इसी तरह जब तक बहुत छोटे ब्लॉक प्राप्त नहीं हो जाते।
ऐसे न्यूनतम तत्वों की लंबाई एक के बराबर हो सकती है, अर्थात वे स्वयं एक क्रमबद्ध सरणी हो सकती हैं, लेकिन यह एक आवश्यक शर्त नहीं है। ब्लॉक का आकार पहले से निर्धारित किया जाता है, और कोई भी उपयुक्त सॉर्टिंग एल्गोरिथम जो छोटे आकार के सरणियों (उदाहरण के लिए, क्विकॉर्ट या इंसर्शन सॉर्ट) के साथ कुशलता से काम करता है, का उपयोग इसे ऑर्डर करने के लिए किया जा सकता है।
ऐसा दिखता है।


// मूल सरणी {34, 95, 10, 2, 102, 70}; // पहला विभाजन {34, 95, 10} और {2, 102, 70}; // दूसरा विभाजन {34} और {95, 10} और {2} और {102, 70}

1-2 तत्वों से युक्त परिणामी ब्लॉकों को व्यवस्थित करना बहुत आसान है।
उसके बाद, आपको पहले से छांटे गए छोटे सरणियों को जोड़ियों में मिलाना होगा, सदस्यों के क्रम को बनाए रखना होगा, जिसे हम पहले ही करना सीख चुके हैं।






पहले चरण का क्रियान्वयन
सरणी का पुनरावर्ती विभाजन नीचे दिखाया गया है।


void mergeSort(T a, long start, long finish) {लंबा विभाजन; अगर(प्रारंभ < समाप्त) { विभाजन=(प्रारंभ + समाप्त) / 2; मर्जसॉर्ट (ए, स्टार्ट, स्प्लिट); मर्जसॉर्ट (ए, स्प्लिट + 1, फिनिश); मर्ज (ए, स्टार्ट, स्प्लिट, फिनिश); } }

इस कोड में क्या होता है:



मर्जसॉर्ट फ़ंक्शन को प्रारंभिक सरणी

a

और क्षेत्र की बाईं और दाईं सीमाओं को क्रमबद्ध किया जाता है (सूचकांक प्रारंभ और

खत्म).



यदि इस खंड की लंबाई एक से अधिक है (

प्रारंभ < समाप्त

), तो इसे दो भागों में विभाजित किया जाता है (सूचकांक द्वारा

विभाजन), और प्रत्येक को पुनरावर्ती रूप से क्रमबद्ध किया जाता है।



बाईं ओर के रिकर्सिव फंक्शन कॉल में, प्लॉट का शुरुआती इंडेक्स और इंडेक्स

split

पास किया जाता है। दाईं ओर, क्रमशः, शुरुआत

(विभाजन + 1) होगी, और अंत मूल खंड की अंतिम अनुक्रमणिका होगी।



फ़ंक्शन

मर्ज

को दो क्रमित क्रम मिलते हैं (

a[शुरू]…a[विभाजन]

और

a[विभाजन +1]…a[finish]) और उन्हें क्रमबद्ध क्रम में मिला देता है।


मर्ज फंक्शन की यांत्रिकी ऊपर चर्चा की गई है।

एल्गोरिदम की सामान्य योजना
मर्ज सॉर्ट सरणी विधि में दो बड़े चरण होते हैं:

बिना क्रमबद्ध मूल सरणी को छोटे टुकड़ों में विभाजित करें।
सॉर्टिंग नियम का पालन करते हुए उन्हें जोड़ियों में इकट्ठा करें।

एक बड़े और जटिल कार्य को कई सरल कार्यों में विभाजित किया जाता है, जिन्हें क्रमिक रूप से हल किया जाता है, जिससे वांछित परिणाम प्राप्त होता है।






विधि मूल्यांकन
मर्ज सॉर्ट की समय जटिलता विभाजित पेड़ की ऊंचाई से निर्धारित होती हैएल्गोरिदम और सरणी में तत्वों की संख्या के बराबर है (एन) बार इसके लॉगरिदम (लॉग एन)। ऐसे अनुमान को लघुगणक कहते हैं।
यह विधि का लाभ और हानि दोनों है। इसके चलने का समय सबसे खराब स्थिति में भी नहीं बदलता है, जब मूल सरणी को उल्टे क्रम में क्रमबद्ध किया जाता है। हालांकि, पूरी तरह से सॉर्ट किए गए डेटा को संसाधित करते समय, एल्गोरिथम समय लाभ प्रदान नहीं करता है।
मर्ज सॉर्ट विधि की मेमोरी लागत को नोट करना भी महत्वपूर्ण है। वे मूल संग्रह के आकार के बराबर हैं। इस अतिरिक्त आवंटित क्षेत्र में, टुकड़ों से एक क्रमबद्ध सरणी इकट्ठी की जाती है।

एल्गोरिदम का कार्यान्वयन
पास्कल मर्ज सॉर्ट नीचे दिखाया गया है।


प्रक्रिया मर्जसॉर्ट (नाम: स्ट्रिंग; var f: टेक्स्ट); वार a1, a2, s, i, j, kol, tmp: पूर्णांक; f1, f2: पाठ; बी: बूलियन बेगिनकोल:=0; असाइन करें (एफ, नाम); रीसेट (एफ); जबकि ईओएफ (एफ) पढ़ना शुरू नहीं करते हैं (एफ, ए 1); इंक (कॉल); अंत; बंद करें (एफ); असाइन करें (f1, '{पहली सहायक फ़ाइल का नाम}'); असाइन करें (f2, '{दूसरी सहायक फ़ाइल का नाम}'); एस:=1; जबकि (s<kol) रीसेट (f) शुरू करते हैं; फिर से लिखना (एफ 1); फिर से लिखना (एफ 2); के लिए i:=1 to kol div 2 do start Read(f, a1); लिखें (एफ 1, ए 1, ''); अंत; अगर (कोल डिव 2) मॉड एस0 तो शुरू करें tmp:=kol div 2; जबकि tmp mod s0 पढ़ना शुरू करें (f, a1); लिखें (एफ 1, ए 1, ''); इंक (टीएमपी); अंत; अंत; जबकि ईओएफ (एफ) शुरू नहीं करते हैं पढ़ें (एफ, ए 2); लिखें (एफ 2, ए 2, ''); अंत; बंद करें (एफ); बंद करें (एफ 1); बंद करें (एफ 2); फिर से लिखना (एफ); रीसेट (एफ 1); रीसेट (एफ 2); पढ़ें (एफ 1, ए 1); पढ़ें (एफ 2, ए 2); जबकि (EOF(f1) नहीं) और (EOF(f2) नहीं) i:=0 शुरू करते हैं; जे:=0; बी:=सच; जबकि (बी) और (ईओएफ (एफ 1) नहीं) और (ईओएफ (एफ 2) नहीं) शुरू करते हैं यदि (ए 1< ए 2) तो शुरू करेंलिखें (एफ, ए 1, ''); पढ़ें (एफ 1, ए 1); इंक (मैं); अंत और शुरू लिखें (एफ, ए 2, ''); पढ़ें (एफ 2, ए 2); इंक (जे); अंत; अगर (i=s) या (j=s) तो b:=false; अंत; यदि बी नहीं तो शुरू करें जबकि (i<s) और (ईओएफ (एफ 1) नहीं) शुरू करें लिखें (एफ, ए 1, ''); पढ़ें (एफ 1, ए 1); इंक (मैं); अंत; जबकि (j<s) और (EOF(f2) नहीं) लिखना शुरू करते हैं (f, a2, ''); पढ़ें (एफ 2, ए 2); इंक (जे); अंत; अंत; अंत; जबकि EOF(f1) नहीं start tmp:=a1; पढ़ें (एफ 1, ए 1); यदि ईओएफ (एफ 1) नहीं है तो लिखें (एफ, टीएमपी, '') और लिखें (एफ, टीएमपी); अंत; जबकि EOF(f2) नहीं start tmp:=a2; पढ़ें (एफ 2, ए 2); यदि ईओएफ (एफ 2) नहीं है तो लिखें (एफ, टीएमपी, '') और लिखें (एफ, टीएमपी); अंत; बंद करें (एफ); बंद करें (एफ 1); बंद करें (एफ 2); एस:=एस2; अंत; मिटाएं (एफ 1); मिटाएं (एफ 2); अंत;

दृष्टि से, एल्गोरिथम का संचालन इस तरह दिखता है (शीर्ष - अनियंत्रित अनुक्रम, नीचे - क्रमित)।






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






सरल मर्ज
सरल मर्ज के साथ, श्रृंखला की लंबाई निश्चित होती है।
इस प्रकार, मूल अवर्गीकृत फ़ाइल में, सभी श्रृंखलाओं में एक तत्व होता है। पहले चरण के बाद, आकार बढ़कर दो हो जाता है। अगला - 4, 8, 16 वगैरह।
यह इस तरह काम करता है:

स्रोत फ़ाइल (f) दो सहायक फ़ाइल में विभाजित है - f1, f2।
उन्हें फिर से एक फ़ाइल (f) में मिला दिया जाता है, लेकिन साथ ही सभी तत्वों की तुलना जोड़े में की जाती है और जोड़े बनाते हैं। इस चरण में श्रृंखला का आकार दो हो जाता है।
चरण 1 दोहराया जाता है।
चरण 2 दोहराया जाता है, लेकिन पहले से ऑर्डर किए गए 2s को सॉर्ट किए गए 4s के रूप में मर्ज कर दिया जाता है।
लूप तब तक जारी रहता है, जब तक कि पूरी फाइल को सॉर्ट नहीं किया जाता है, प्रत्येक पुनरावृत्ति पर श्रृंखला को बढ़ाता है।

आप कैसे जानते हैं कि एक साधारण मर्ज के साथ बाहरी छँटाई पूरी हो गई है?

नई श्रृंखला की लंबाई (विलय के बाद) तत्वों की कुल संख्या से कम नहीं;
सिर्फ एक एपिसोड बचा है;
सहायक फ़ाइल f2 खाली रह गई थी।

एक साधारण मर्ज के नुकसान हैं: चूंकि प्रत्येक मर्ज पास पर रन की लंबाई तय होती है, आंशिक रूप से ऑर्डर किए गए डेटा को पूरी तरह से यादृच्छिक डेटा के रूप में संसाधित होने में उतना ही समय लगेगा।

प्राकृतिक संलयन
यह विधि लंबाई को सीमित नहीं करती हैश्रृंखला, लेकिन अधिकतम संभव चुनती है।
छँटाई एल्गोरिथ्म:

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

श्रृंखला का आकार निश्चित न होने के कारण अनुक्रम के अंत को एक विशेष वर्ण से अंकित करना आवश्यक है। इसलिए, विलय करते समय, तुलनाओं की संख्या बढ़ जाती है। इसके अलावा, सहायक फाइलों में से एक का आकार मूल के आकार के करीब हो सकता है।
औसतन, बाहरी प्रकार के साथ साधारण मर्ज की तुलना में प्राकृतिक मर्ज अधिक कुशल है।

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





वीडियो मर्ज सॉर्ट एल्गोरिथम के संचालन को स्पष्ट रूप से प्रदर्शित करता है।