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

इस लेख में, मैं इस एल्गोरिथम के पीछे की अवधारणा के बारे में बात करने जा रहा हूं और आपको जावास्क्रिप्ट में एक उदाहरण दिखाऊंगा।

अवधारणा की व्याख्या

एक फूट डालो और जीतो एल्गोरिथ्म एक समस्या को छोटी समस्याओं में तब तक तोड़ देता है जब तक कि ये हल करने के लिए पर्याप्त सरल न हो जाएं। मूल समस्या का समाधान देने के लिए उप-समस्याओं के समाधान को जोड़ दिया जाता है।

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

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

आप नीचे देख सकते हैं कि कैसे हम पुनरावर्ती रूप से सरणी को छोटे सरणियों में विभाजित करते हैं जब तक कि हमारे पास केवल एक आइटम की सरणियाँ न हों।

[1,9,3,8,6,5,7,4,2]
[1,9,3,8]              [6,5,7,4,2]
[1,9]       [3,8]       [6,5]       [7,4,2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]     [4,2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]

[1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]     [2,4]
[1,9]       [3,8]       [5,6]       [2,4,7]
[1,3,8,9]              [2,4,5,6,7]
[1,2,3,4,5,6,7,8,9]

const mergeSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  return mergeArray(
    mergeSort(arr.slice(0, middle)), 
    mergeSort(arr.slice(middle))
  );
};
const mergeArray = (left, right) => {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
return [...result, ...left, ...right];
};
const unorderedArray = [1, 9, 3, 8, 6, 5, 7, 4, 2];
console.log(mergeSort(unorderedArray)); // Returns ordered array

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

खैर, इसके लिए बस इतना ही। आप क्या सोचते हैं मुझे बताओ। हैप्पी कोडिंग!

Plainenglish.io पर अधिक सामग्री