मर्ज-सॉर्ट करें
मर्ज सॉर्ट एक डिवाइड-एंड-कॉनकॉर टाइप सॉर्टिंग-एल्गोरिदम का एक उदाहरण है। मर्ज सॉर्ट का इनपुट कुछ तत्वों की एक सरणी है, जिन्हें आमतौर पर कम से कम से सबसे बड़े तक व्यवस्थित करने की आवश्यकता होती है।
मर्ज सॉर्ट में अनुसरण करने के चरण
- मर्ज सॉर्ट सरणी को दो उप सरणियों में विभाजित करता है और बाद में प्रत्येक सरणी को अन्य दो सरणियों में विभाजित करता है और इसी तरह जब तक एकल तत्व सरणियों का एक गुच्छा नहीं छोड़ा जाता है। उदाहरण के लिए, निम्नलिखित उदाहरण में सरणी [4,7,5,9,1,3,8,2] एकल सरणी तत्वों में विभाजित होती है जैसे [4], [7], [5], [9], [1], [3], [8], [2]।
- यह सरणियों की तुलना इस तरह से करना शुरू करता है कि दो सरणियों की तुलना और संयोजन किया जाता है। निम्नलिखित उदाहरण में, यह एक समय में दो सरणियों की तुलना करता है [4], [7] की तुलना और संयोजन किया जाता है, फिर [5], [9] की तुलना और संयोजन किया जाता है और इसी तरह कि सरणियाँ [4,7], [ 5,9], [1,3], [2,8] बनते हैं।
- यह उसी तरह से होता है जैसे दो-दो सरणियों की तुलना की जाती है और दो सरणियों को बनाने के लिए संयोजित किया जाता है। निम्नलिखित उदाहरण में [4,7] और [5,9] की तुलना [4,5,7,9] के रूप में एक सरणी प्राप्त करने के लिए की जाती है और एक सरणी बनाने के लिए अन्य दो सरणियों के साथ भी ऐसा ही है [1, 2,3,8].
- यहाँ वही नियम लागू है जो शेष दो सरणियों की तुलना करता है और एक अंतिम सरणी प्राप्त करने के लिए [1,2,3,4,5,7,8,9] है।
उदाहरण
<html>
<body>
<script>
function mSort (array) {
if (array.length === 1) {
return array // return once we hit an array with a single item
}
const middle = Math.floor(array.length / 2) // get the middle item of the array rounded down
const left = array.slice(0, middle) // items on the left side
const right = array.slice(middle) // items on the right side
document.write(middle);
return merge(
mSort(left),
mSort(right)
)
}
// compare the arrays item by item and return the concatenated result
function merge (left, right) {
let result = []
let leftIndex = 0
let rightIndex = 0
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex])
leftIndex++
document.write("</br>");
} else {
result.push(right[rightIndex])
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
const list = [4,7,5,9,1,3,8,2]
document.write(mSort(list));
</script>
</body>
</html> आउटपुट
1,2,3,4,5,7,8,9