मर्ज सॉर्ट डिवाइड एंड कंक्वर तकनीक पर आधारित एक सॉर्टिंग तकनीक है। इसका सबसे खराब स्थिति में समय जटिलता O(n log n) है। लेकिन यह अतिरिक्त लागत के साथ आता है क्योंकि यह एल्गोरिदम अतिरिक्त O(n) मेमोरी लेता है।
आइए देखें कि हम इस एल्गोरिदम को कैसे लागू करने जा रहे हैं। हम 2 फंक्शन बनाएंगे, mergeSort और merge।
merge - यह फंक्शन 2 आर्गुमेंट्स लेता है, ये 2 आंशिक ऐरे हैं जिन्हें यह सही क्रम में एलिमेंट्स इन्सर्ट करके एक में जोड़ता है।
mergeSort - यह फंक्शन ऐरे के बाएं और दाएं हिस्सों पर mergeSort को रिकर्सिवली कॉल करता है और फिर इन ऐरे भागों को एक साथ जोड़ने के लिए merge का उपयोग करता है। एक बार जब हम कार्यान्वयन देखेंगे तो यह बहुत स्पष्ट हो जाएगा।
आइए merge फंक्शन से शुरू करें और सीधे कोड में गोता लगाएं -
उदाहरण
function merge(left, right) { let mergedArr = []; let i = 0; let j = 0; // दोनों ऐरे में से किसी एक के अंत तक पहुंचने तक मर्ज करने का प्रयास करें while (i < left.length && j < right.length) { if (compare(left[i], right[j])) { mergedArr.push(left[i]); i++; } else { mergedArr.push(right[j]); j++; } } // यदि left 1, 2, 3, 5 था और right 4, 6, 7, 9 था // ऊपर का फॉर लूप लेफ्ट ऐरे के अंत तक पहुंचने पर रुक जाएगा // लेफ्ट ऐरे में 3 एलिमेंट्स छोड़कर // शेष एलिमेंट्स को किसी भी ऐरे से जोड़ने के लिए, // हमें लेफ्ट में i से अंत तक और राइट में j से अंत तक // एलिमेंट्स को मर्ज्ड ऐरे में जोड़ने की आवश्यकता है 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]
अब हम इस फंक्शन का उपयोग अपने मर्जसॉर्ट फंक्शन में पूरे ऐरे को वास्तव में सॉर्ट करने के लिए करेंगे।
हम mergeSort के लिए एक इनर फंक्शन बनाएंगे जिसे हम एक आउटर फंक्शन के साथ रैप करेंगे ताकि हमारा कम्पेरेटर उपलब्ध हो ताकि हमारा फंक्शन एक्सटेंसिबल हो। आइए इस इनर फंक्शन को देखें -
उदाहरण
function mergeSortInner(arr) { if (arr.length < 2) { return arr; } let mid = Math.floor(arr.length / 2); // 0 से mid - 1 एलिमेंट्स से ऐरे बनाएं let left = arr.slice(0, mid); // mid से अंतिम एलिमेंट तक ऐरे बनाएं let right = arr.slice(mid); // बाएं आधे को सॉर्ट करें, दाएं आधे को सॉर्ट करें, // सॉर्टेड ऐरे को मर्ज करें और लौटाएं 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 } ]
क्विक सॉर्ट
क्विक सॉर्ट एक अत्यधिक कुशल सॉर्टिंग एल्गोरिदम है और डेटा के ऐरे को छोटे ऐरे में विभाजित करने पर आधारित है। एक बड़े ऐरे को दो ऐरे में विभाजित किया जाता है जिनमें से एक निर्दिष्ट मान से छोटे मान रखता है, कहें पिवट, जिसके आधार पर विभाजन किया जाता है और दूसरा ऐरे पिवट मान से बड़े मान रखता है।
क्विक सॉर्ट एक ऐरे को पार्टीशन करता है और फिर दो परिणामी सबऐरे को सॉर्ट करने के लिए खुद को दो बार रिकर्सिवली कॉल करता है। यह एल्गोरिदम बड़े आकार के डेटा सेट के लिए काफी कुशल है क्योंकि इसकी औसत और सबसे खराब स्थिति की जटिलता O(n²) है, जहां n आइटम्स की संख्या है।
पार्टीशन प्रक्रिया
निम्नलिखित एनिमेटेड प्रतिनिधित्व बताता है कि ऐरे में पिवट मान कैसे खोजें। https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif
पिवट मान लिस्ट को दो भागों में विभाजित करता है। और रिकर्सिवली, हम प्रत्येक सब-लिस्ट के लिए पिवट ढूंढते हैं जब तक सभी लिस्ट में केवल एक एलिमेंट नहीं होता।
पार्टीशनिंग में हम क्या करते हैं कि हम ऐरे से पहला एलिमेंट चुनते हैं (रैंडमाइज्ड क्विक सॉर्ट में रैंडम एलिमेंट्स) और फिर बाकी ऐरे की तुलना इस एलिमेंट से करते हैं। हम फिर इस एलिमेंट से कम सभी एलिमेंट्स को उस पिवट इंडेक्स के बाईं ओर ले जाते हैं जिसे हम पिवट इंडेक्स कहते हैं और इस एलिमेंट से बड़े मानों को पिवट इंडेक्स के दाईं ओर। इसलिए जब हम अंत तक पहुंचते हैं, तो पिवट एलिमेंट (पहला एलिमेंट) अपनी सही स्थिति में रखा जाता है।
ऐसा इसलिए है क्योंकि इससे बड़े सभी एलिमेंट्स दाईं ओर हैं और इससे कम बाईं ओर हैं जिससे यह एलिमेंट सही स्थान पर रहता है। हम इस पार्टीशनिंग प्रक्रिया को बाएं और दाएं सब ऐरे पर रिकर्सिवली कॉल करके पार्टीशन करके सॉर्टिंग में मदद करने के लिए बढ़ाते हैं।
हम पार्टीशन फंक्शन को निम्नानुसार लागू कर सकते हैं -
उदाहरण
function partition(arr, low, high, compare) { let pivotIndex = low + 1; for (let i = pivotIndex; i < high; i++) { if (compare(arr[i], arr[low])) { // पिवट से कम संख्या को स्वैप करें swap(arr, i, pivotIndex); pivotIndex += 1; } } // पिवट को उसकी सही स्थिति में रखें swap(arr, pivotIndex - 1, low); // पिवट की स्थिति लौटाएं 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) { // ऐरे को पार्टीशन करें let mid = partition(arr, low, high, compare); // बाएं आधे को रिकर्सिवली सॉर्ट करें QuickSort(arr, low, mid, compare); // दाएं आधे को रिकर्सिवली सॉर्ट करें 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 ]
