मर्ज सॉर्ट डिवाइड और जीत तकनीक पर आधारित एक छँटाई तकनीक है। इसमें (एन लॉग एन) की सबसे खराब स्थिति समय जटिलता है। लेकिन यह स्थान के मामले में एक अतिरिक्त लागत के साथ आता है क्योंकि यह एल्गोरिथ्म एक अतिरिक्त O(n) मेमोरी लेता है।
अब आइए देखें कि हम इस एल्गोरिथम को कैसे लागू करने जा रहे हैं। हम 2 फ़ंक्शन बनाएंगे, मर्ज सॉर्ट और मर्ज करेंगे।
मर्ज करें - यह फ़ंक्शन 2 तर्क लेता है, ये 2 आंशिक सरणियाँ हैं जिन्हें यह सही क्रम में तत्वों को सम्मिलित करके एक में समेट देता है।
मर्जसॉर्ट करें - यह फ़ंक्शन सरणी के बाएँ और दाएँ हिस्सों पर mergeSort को बार-बार कॉल करता है और फिर इन सरणी भागों को एक साथ संयोजित करने के लिए मर्ज का उपयोग करता है। एक बार जब हम कार्यान्वयन को देखेंगे तो यह और अधिक स्पष्ट हो जाएगा।
आइए मर्ज फ़ंक्शन से शुरू करें और सीधे कोड में गोता लगाएँ -
उदाहरण
function merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
} यह फ़ंक्शन 2 क्रमबद्ध सरणियाँ लेगा और उन्हें O(n) समय में इस तरह मिला देगा कि वे बड़े सरणी के रूप में क्रमबद्ध रहें। विधि की गहराई से व्याख्या के लिए कोड टिप्पणियों का संदर्भ लें। आप इसका परीक्षण कर सकते हैं -
उदाहरण
let a1 = [1, 2, 3, 5] let a2 = [4, 6, 8, 9] console.log(merge(a1, a2))
आउटपुट
[1, 2, 3, 4, 5, 8, 9]
अब हम इस फ़ंक्शन का उपयोग हमारे मर्जसॉर्ट फ़ंक्शन में वास्तव में संपूर्ण सरणी को सॉर्ट करने के लिए करेंगे।
हम मर्जसॉर्ट के लिए एक आंतरिक फ़ंक्शन बनाएंगे जिसे हम अपने तुलनित्र को उपलब्ध कराने के लिए एक बाहरी फ़ंक्शन के साथ लपेटेंगे ताकि हमारा फ़ंक्शन एक्स्टेंसिबल हो। आइए इस आंतरिक कार्य पर एक नजर डालते हैं -
उदाहरण
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
// Create an array from 0 to mid - 1 elements
let left = arr.slice(0, mid);
// Create an array from mid to the last element
let right = arr.slice(mid);
// Sort the left half, sort the right half,
// merge the sorted arrays and return
return merge(mergeSortInner(left), mergeSortInner(right));
} यह फ़ंक्शन एक सरणी लेता है इसे दो में तोड़ता है, उन्हें अलग-अलग सॉर्ट करता है और फिर एक मर्ज किए गए सरणी को वापस लौटाता है।
आइए एक परीक्षण के साथ पूरा कोड देखें -
उदाहरण
function mergeSort(arr, compare = (a, b) => a < b) {
function merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSortInner(left), mergeSortInner(right));
}
// Call inner mergesort to sort and return the array for us.
return mergeSortInner(arr);
}
You can test this using:
let arr = [5, 8, 9, 12, -8, 31, 2];
// Sort Array elements in increasing order
arr = mergeSort(arr);
console.log(arr);
// Sort Array elements in decreasing order
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);
arr = [
{
name: "Harry",
age: 20
},
{
name: "Jacob",
age: 25
},
{
name: "Mary",
age: 12
}
];
// Sort Array elements in increasing order alphabetically by names
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// Sort Array elements in decreasing order of ages
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr); आउटपुट
[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 },
{ name: 'Mary', age: 12 }
]
[
{ name: 'Mary', age: 12 },
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 }
] त्वरित क्रमित करें
त्वरित छँटाई एक अत्यधिक कुशल छँटाई एल्गोरिथ्म है और यह डेटा की सरणी को छोटे सरणियों में विभाजित करने पर आधारित है। एक बड़े सरणी को दो सरणियों में विभाजित किया जाता है, जिनमें से एक में निर्दिष्ट मान से छोटे मान होते हैं, जैसे कि पिवट, जिसके आधार पर विभाजन किया जाता है और दूसरा सरणी पिवट मान से अधिक मान रखता है।
त्वरित क्रम एक सरणी को विभाजित करता है और फिर दो परिणामी उप-सरणी को सॉर्ट करने के लिए स्वयं को दो बार पुनरावर्ती रूप से कॉल करता है। यह एल्गोरिथम बड़े आकार के डेटा सेट के लिए काफी कुशल है क्योंकि इसकी औसत और सबसे खराब स्थिति जटिलता Ο(n2) की है, जहां n आइटमों की संख्या है।
विभाजन प्रक्रिया
निम्नलिखित एनिमेटेड प्रतिनिधित्व बताता है कि किसी सरणी में पिवट मान कैसे प्राप्त करें।
पिवट मान सूची को दो भागों में विभाजित करता है। और पुनरावर्ती रूप से, हम प्रत्येक उप-सूचियों के लिए धुरी पाते हैं जब तक कि सभी सूचियों में केवल एक तत्व न हो।
विभाजन में हम जो करते हैं वह यह है कि हम सरणी से पहले तत्व का चयन करते हैं (यादृच्छिक त्वरित क्रम में यादृच्छिक तत्व) और फिर इस तत्व के साथ शेष सरणी की तुलना करते हैं। फिर हम इस तत्व से कम के सभी तत्वों को पिवट इंडेक्स के बाईं ओर ले जाते हैं और इससे अधिक मान पिवट इंडेक्स के दाईं ओर ले जाते हैं। इसलिए जब हम अंत तक पहुँचते हैं, तो धुरी तत्व (प्रथम तत्व) को उसकी सही स्थिति में रखा जाता है।
इसका कारण यह है कि इससे बड़े सभी तत्व दायीं ओर हैं और इससे कम बायीं ओर इस तत्व को सही जगह पर छोड़ देते हैं। हम इस विभाजन प्रक्रिया को बाएँ और दाएँ उप सरणियों पर विभाजन को पुनरावर्ती रूप से कॉल करके छाँटने में मदद करने के लिए बढ़ाते हैं।
हम विभाजन फ़ंक्शन को निम्नानुसार कार्यान्वित कर सकते हैं -
उदाहरण
function partition(arr, low, high, compare) {
let pivotIndex = low + 1;
for (let i = pivotIndex; i < high; i++) {
if (compare(arr[i], arr[low])) {
// Swap the number less than the pivot
swap(arr, i, pivotIndex);
pivotIndex += 1;
}
}
// Place the pivot to its correct position
swap(arr, pivotIndex - 1, low);
// Return pivot's position
return pivotIndex - 1;
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
You can test the partition function using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr); आउटपुट
4 [ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]
ध्यान दें कि 5 के बाईं ओर के तत्व 5 से कम हैं और इसके दाईं ओर 5 से अधिक हैं। हम यह भी देखते हैं कि 5 का सूचकांक 4 है।
अब देखते हैं कि क्विक सॉर्ट कैसे काम करता है -
यदि हमारे पास 1 तत्व से अधिक विंडो है, तो हम निम्न से उच्च तक सरणी पर विभाजन को कॉल करते हैं, लौटाई गई अनुक्रमणिका लेते हैं और सरणी के बाएं और दाएं हिस्सों पर क्विकॉर्ट को कॉल करने के लिए इसका उपयोग करते हैं।
उदाहरण
function QuickSort(arr, low, high, compare = (l, r) => l < r) {
if (high - low > 0) {
// Partition the array
let mid = partition(arr, low, high, compare);
// Recursively sort the left half
QuickSort(arr, low, mid, compare);
// Recursively sort the right half
QuickSort(arr, mid + 1, high, compare);
}
}
You can test this using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr); आउटपुट
[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]