सी ++ प्रोग्राम लिंक्ड लिस्ट पर मर्ज सॉर्ट एल्गोरिथम को लागू करने के लिए

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

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

मर्ज सॉर्ट तकनीक की जटिलता

• समय की जटिलता - O(n log n) सभी मामलों के लिए

• अंतरिक्ष जटिलता -ओ(एन)

इनपुट - क्रमबद्ध सूची:14 20 78 98 20 45आउटपुट - क्रमबद्ध करने के बाद सरणी:14 20 20 45 78 98

एल्गोरिदम

मर्ज लिस्ट(ll1, ll2)

इनपुट − इसमें दो लिंक की गई सूचियां ll1 और ll2 होती हैं

आउटपुट - मर्ज की गई सूची

शुरू करें यदि ll1 खाली है, तो ll2 लौटाएं यदि ll2 खाली है, तो ll1 लौटाएं यदि डेटा (ll1) <=डेटा (ll2), तो new_head =ll1; अगला (new_head) =मर्जलिस्ट (अगला (ll1), ll2) अन्य new_head =ll2; अगला (new_head) =मर्जलिस्ट (ll1, अगला (ll2)) new_headEnd लौटाएं

split_list(start, ll1, ll2)

इनपुट - एक लिंक्ड सूची का प्रारंभ सूचक, दो आउटपुट तर्क ll1 और ll2

आउटपुट - लिंक की गई सूची से उत्पन्न दो लिंक की गई सूची

धीमी गति से शुरू करें:=तेजी से शुरू करें:=अगला(शुरू) जबकि उपवास शून्य नहीं है, तेजी से करें:=अगला(तेज) यदि उपवास शून्य नहीं है, तो धीमा:=अगला(धीमा) तेज:=अगला(तेज) अंत जबकि ll1:=ll2 शुरू करें:=अगला(धीमा) अगला(धीमा) :=nullEnd

मर्जसॉर्ट(प्रारंभ)

इनपुट - लिंक की गई सूची

आउटपुट - क्रमबद्ध लिंक की गई सूची

शुरुआत सिर =शुरू करें अगर सिर शून्य है या अगला (सिर) शून्य है, तो स्प्लिट_लिस्ट (हेड, ll1, ll2) मर्जसॉर्ट (ll1) मर्जसॉर्ट (ll2) शुरू करें:=मर्जलिस्ट (ll1, ll2) समाप्त करें।> 
सोर्स कोड (C++)
 
#includeनामस्थान का उपयोग करना;वर्ग नोड {//डेटा को स्टोर करने के लिए नोड को परिभाषित करें और अगला पता सार्वजनिक करें:int डेटा; नोड * अगला;}; शून्य प्रदर्शन (वर्ग नोड * प्रारंभ) {नोड * पी =प्रारंभ; // वर्तमान नोड सिर पर सेट है जबकि (पी! =न्यूल) {// जब तक वर्तमान नोड न्यूल कॉउट नहीं है <<पी -> डेटा <<""; पी =पी -> अगला; // अगले नोड पर जाएं}}नोड* getNode(int d) {नोड* अस्थायी =नया नोड; अस्थायी -> डेटा =डी; अस्थायी -> अगला =NULL; वापसी अस्थायी;} नोड * मर्जलिस्ट (नोड * ll1, नोड * ll2) {// दो सॉर्ट की गई सूची को मर्ज करने के लिए फ़ंक्शन नोड * न्यूहेड =न्यूल; अगर (ll1 ==NULL) वापसी ll2; अगर (ll2 ==NULL) वापसी ll1; // सूचियों को पुनरावर्ती रूप से मर्ज करें यदि (ll1 -> डेटा <=ll2 -> डेटा) {न्यूहेड =ll1; न्यूहेड -> अगला =मर्जलिस्ट (ll1-> अगला, ll2); } और { न्यूहेड =ll2; न्यूहेड -> अगला =मर्जलिस्ट (ll1, ll2-> अगला); } न्यूहेड लौटाएं;} शून्य विभाजन सूची (नोड * प्रारंभ, नोड ** ll1, नोड ** ll2) {// फ्लायोड के कछुआ एल्गोरिथ्म नोड के समान * धीमा =प्रारंभ; नोड * तेज =प्रारंभ -> अगला; जबकि (तेज़! =NULL) {तेज़ =तेज़ -> अगला; अगर (तेज़! =न्यूल) {धीमा =धीमा -> अगला; तेज =तेज -> अगला; } } *ll1 =प्रारंभ; *ll2 =धीमा -> अगला; // धीमी गति से विभाजन -> अगला =नल;} शून्य मर्जसॉर्ट (नोड ** प्रारंभ) {नोड * सिर =* प्रारंभ; नोड* ll1,*ll2; // आधार मामला अगर (सिर ==NULL || सिर-> अगला ==NULL) {वापसी; } स्प्लिटलिस्ट (हेड,&ll1,&ll2); // सूची को दो हिस्सों में विभाजित करें // बाएं और दाएं सबलिस्ट्स को सॉर्ट करें मर्जसॉर्ट (&ll1); मर्जसॉर्ट (&ll2); // दो क्रमबद्ध सूची मर्ज करें * प्रारंभ =मर्जलिस्ट (ll1, ll2); वापसी;}int main() { cout <<"लिंक की गई सूची बनाना:" <> के; नोड * हेड =गेटनोड (के); // buliding सूची, पहला नोड cin>> k; अस्थायी =सिर; जबकि (के) {curr =getNode (के); अस्थायी -> अगला =वक्र; // प्रत्येक नोड को जोड़ना अस्थायी =अस्थायी -> अगला; सिनेमा>> के; } cout<<"छँटाई से पहले:" < 
आउटपुट
 
लिंक की गई सूची बनाना:सूची बनाना बंद करने के लिए 0 दर्ज करें, अन्यथा कोई भी पूर्णांक दर्ज करें8954156474981024260सॉर्ट करने से पहले:89 54 15 64 74 98 10 24 26सॉर्ट करने के बाद:10 15 24 26 54 64 74 89 98