Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> JavaScript

JavaScript में मर्ज सॉर्ट इम्प्लीमेंटेशन


मर्ज सॉर्ट (Merge Sort)

डिवाइड-एंड-कॉन्कर एल्गोरिदम: ऐरे को आधा-आधा विभाजित करें जब तक सिंगल एलिमेंट्स न रह जाएं, फिर सॉर्टेड मर्ज करें। समय जटिलता: O(n log n) (सभी केसेस में)।

एल्गोरिदम चरण

  1. विभाजन: ऐरे को दो भागों में बांटें, पुनरावर्ती रूप से जारी रखें
  2. विजय: सिंगल-एलिमेंट ऐरे पहले से सॉर्टेड हैं
  3. मर्ज: दो सॉर्टेड ऐरे को मर्ज करें

उदाहरण: [4,7,5,9,1,3,8,2]

विभाजन: [4,7,5,9] [1,3,8,2]
       [4,7] [5,9]   [1,3] [8,2]
       [4][7] [5][9] [1][3] [8][2]

मर्ज:   [4,7] [5,9]   [1,3] [2,8]
       [4,5,7,9]     [1,2,3,8]
       [1,2,3,4,5,7,8,9]  ← फाइनल

इम्प्लीमेंटेशन

<html> <body> <script>
  function mergeSort(array) {
    // बेस केस: सिंगल एलिमेंट या खाली
    if (array.length <= 1) return array;
    
    // विभाजन
    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);
    
    // पुनरावर्ती कॉल + मर्ज
    return merge(mergeSort(left), mergeSort(right));
  }
  
  // दो सॉर्टेड ऐरे मर्ज करें
  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++;
      } 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("मूल: " + list + "<br>");
  document.write("सॉर्टेड: " + mergeSort(list));
</script> </body> </html>

आउटपुट

मूल: 4,7,5,9,1,3,8,2
सॉर्टेड: 1,2,3,4,5,7,8,9

विशेषताएं

पहलूविवरण
समय जटिलताO(n log n) - बेस्ट, एवरेज, वर्स्ट
स्पेस जटिलताO(n) - सहायक ऐरे
स्थिर (Stable)हाँ - समान एलिमेंट्स का क्रम बरकरार
इन-प्लेसनहीं (आमतौर पर)

उपयोग के मामले

  • लिंक्ड लिस्ट्स सॉर्टिंग (O(1) स्पेस संभव)
  • एक्सटर्नल सॉर्टिंग (बड़ी फाइल्स)
  • जब स्टेबल सॉर्ट चाहिए
  • फंक्शनल प्रोग्रामिंग (इम्म्यूटेबल डेटा)

JavaScript बिल्ट-इन

<script>
// प्रोडक्शन में बिल्ट-इन उपयोग करें (हाइली ऑप्टिमाइज़्ड)
var arr = [4, 7, 5, 9, 1, 3, 8, 2];
arr.sort((a, b) => a - b);  // [1, 2, 3, 4, 5, 7, 8, 9]
</script>
  1. जावास्क्रिप्ट में Array.prototype.sort() मेथड जावास्क्रिप्ट में Array.prototype.sort() मेथड

    जावास्क्रिप्ट Array.prototype.sort() मेथड का उपयोग एरे को सॉर्ट करने के लिए किया जाता है। सॉर्टिंग का क्रम अल्फाबेटिक, न्यूमेरिक, आरोही या अवरोही हो सकता है। Array.prototype.sort() मेथड के लिए कोड निम्नलिखित है: उदाहरण <!DOCTYPE html> <html lang=en> <head> <meta charset=UTF-8 /

  1. जावास्क्रिप्ट में एरे को रिड्यूस कैसे करें? जावास्क्रिप्ट में एरे को रिड्यूस कैसे करें?

    जावास्क्रिप्ट में एरे को रिड्यूस करने के लिए कोड निम्नलिखित है: उदाहरण <!DOCTYPE html> <html lang=en> <head> <meta charset=UTF-8 /> <meta name=viewport content=width=device-width, initial-scale=1.0 /> <title>Document</title> <style>    body

  1. - C++ प्रोग्राम: मर्ज सॉर्ट लागू करना

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