मैं यह समझने की कोशिश कर रहा हूं कि जावास्क्रिप्ट मर्ज सॉर्ट फ़ंक्शन कैसे काम करता है। और मैं यह समझने में संघर्ष करता हूं कि रिकर्सिव फ़ंक्शन कैसे काम करता है। यह कोड है:

const mergeSort = array => {
  if (array.length < 2) {
    //function stop here
    return array
  }

  const middle = Math.floor(array.length / 2);
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  return merge(mergeSort(leftSide), mergeSort(rightSide))

};

const merge = (left, right) => {
  const result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift);
    }
  }

  while(left.length) result.push(left.shift());

  while(right.length) result.push(right.shift());

  return result;
}
mergeSort([5,3,8,10,4,1])
3
shane_00 18 फरवरी 2020, 22:23
1
ध्यान दें कि सभी मान या तो वर्तमान फ़ंक्शन कॉल के लिए स्थानीय हैं या इसे पास किए गए पैरामीटर हैं। इसलिए [5] और [3, 8] को सॉर्ट करने के बाद, return merge... लाइन merge को [5] और [3, 8] के साथ कॉल करती है, जो [3, 5, 8] लौटाती है। दाहिने आधे हिस्से में कुछ ऐसा ही होता है: [10] वापस आ जाता है, [4, 1] को [1, 4] में सॉर्ट किया जाता है और फिर [10] और [1, 4] को [1, 4, 10] में मिला दिया जाता है। . अंत में [3, 5, 8] और [1, 4, 10] को [1, 3, 4, 5, 8, 10] में मिला दिया जाता है। प्रत्येक पुनरावर्ती कॉल रास्ते में स्थानीय चर की अपनी प्रति रखता है।
 – 
Scott Sauyet
18 फरवरी 2020, 22:34
1
इसे किसी कागज़ पर लिखें: आप [5, 3, 8, 10, 4, 1] से शुरू करते हैं, जो mergeSort में दो सरणियों में विभाजित हो जाता है। उन दोनों सरणियों को (पुनरावर्ती) mergeSort में फिर से पास किया जाता है, जहां [5, 3, 8] [5] और [3, 8] बन जाते हैं। [5] के लिए हम कर चुके हैं, और यह वैसे ही वापस आ जाता है। [3,8] के लिए, हम फिर से रिकर्स करते हैं, और वे [3] और [8] के रूप में वापसी करते हैं। उन्हें merged मिलता है: मर्ज चरण के दौरान क्या होता है? इसे लिखें: यदि आप किसी एल्गोरिथम को समझना चाहते हैं तो यह एक महत्वपूर्ण अभ्यास है।
 – 
Mike 'Pomax' Kamermans
18 फरवरी 2020, 22:36
1
लेकिन पहले मर्ज को उस मर्ज (3, 8) की तरह कहा जाता है, फिर निष्पादित होता है लेकिन फ़ंक्शन स्वयं इन मानों को नहीं रख सकता है, फिर यह 5 के साथ फिर से निष्पादित होता है लेकिन मुझे नहीं पता कि 5 कैसे पारित किया जाता है, इसे विलय नहीं किया जा सकता है ([3,8,5 ]) क्योंकि mergeSort केवल एक मान देता है...
 – 
shane_00
18 फरवरी 2020, 22:41
1
हे माइक, मर्ज फ़ंक्शन या मर्ज के अंदर बंटवारे को केवल एक पैरामीटर के साथ बुलाया जाता है?
 – 
shane_00
18 फरवरी 2020, 22:43
- मर्ज को दो पैरामीटर के साथ बुलाया जा रहा है, प्रत्येक पैरामीटर एक सरणी है, और मर्ज एक मर्ज किए गए सरणी को लौटाता है। मर्ज सॉर्ट को लागू करने का यह एक बहुत ही अक्षम तरीका है। दूसरे सरणी का एक बार आवंटन करना बेहतर होगा, फिर दो सरणी के बीच आगे और पीछे विलय करें, सरणी और अनुक्रमणिका को पैरामीटर के रूप में पास करें।
 – 
rcgldr
19 फरवरी 2020, 01:46

3 जवाब

रिकर्सन को समझने के लिए आप इंडेंटेशन के साथ सभी रिकर्सन स्तरों का पता लगा सकते हैं। उदाहरण के लिए:

const mergeSort = (array, level) => {
  logWithLevel(level, "Start sort array " + array);
  if(array.length < 2) {
    //function stop here
    logWithLevel(level, "Finish sort array " + array);
    return array;
  }

  const middle = Math.floor(array.length / 2);
  logWithLevel(level, "middle element is " + array[middle])
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  var result = merge(mergeSort(leftSide, level + 1), mergeSort(rightSide, level + 1));
  logWithLevel(level, "Finish sort array " + result);
  return result;
};

const merge = (left, right) => {
  const result = [];

  while(left.length && right.length){
    if(left[0] <= right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }

  while(left.length) result.push(left.shift());

  while(right.length) result.push(right.shift());

  return result;
}

const logWithLevel = (level, data) => {
    var s = ""
    for (i = 0; i < level; i++) {
        s += "    ";
    }
    console.log(s + data);
}

और परिणाम:

> mergeSort([5,3,8,10,4,1], 0)
    Start sort array 5,3,8,10,4,1
    middle element is 10
        Start sort array 5,3,8
        middle element is 3
            Start sort array 5
            Finish sort array 5
            Start sort array 3,8
            middle element is 8
                Start sort array 3
                Finish sort array 3
                Start sort array 8
                Finish sort array 8
            Finish sort array 3,8
        Finish sort array 3,5,8
        Start sort array 10,4,1
        middle element is 4
            Start sort array 10
            Finish sort array 10
            Start sort array 4,1
            middle element is 1
                Start sort array 4
                Finish sort array 4
                Start sort array 1
                Finish sort array 1
            Finish sort array 1,4
        Finish sort array 1,4,10
    Finish sort array 1,3,4,5,8,10
3
Evgeniy Mironov 19 फरवरी 2020, 02:43

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

मर्ज सॉर्ट में, हम सरणी को छोटे सरणी में विभाजित कर रहे हैं जब तक कि इसका आकार 1 न हो और आकार 1 की एक सरणी पहले से ही सॉर्ट की गई हो। इसके बाद, हम छोटे एरे को इस तरह से मर्ज कर रहे हैं कि नए बनाए गए एरे को भी सॉर्ट किया जाए।

आरेख में आप चौथे स्तर में देख सकते हैं कि सभी सबअरे आकार 1 के हैं और वहां से हम सबएरे को मर्ज कर रहे हैं।

यहां छवि विवरण दर्ज करें छवि स्रोत: GeekForGeeks

function mergeSort(input) {
  const {length:arraySize} = input;
  if (arraySize < 2) return input;
  const mid = Math.floor(arraySize/2);
  const sortedLeftArray = mergeSort(input.slice(0,mid));
  const sortedRightArray = mergeSort(input.slice(mid, arraySize));
  return merge(sortedLeftArray, sortedRightArray);
}

function merge (left, right){
  let result = []
  while(left.length && right.length){
    if(left[0]< right[0]){
      result.push(left.shift())
    }else{
      result.push(right.shift())
    }
  }
  /* Either left/right array will be empty or both */
  return [...result, ...left, ...right];
}

console.log(mergeSort([5,3,8,10,4,1]))
0
Mohammed Ashfaq 9 सितंबर 2020, 15:04
3
ओपी कोड की व्याख्या की तलाश में है, बिना किसी स्पष्टीकरण के अधिक कोड नहीं ...
 – 
Heretic Monkey
16 जून 2020, 17:41
1
हालांकि यह कोड समस्या का समाधान कर सकता है, एक अच्छे उत्तर से यह स्पष्ट होना चाहिए कि कोड क्या करता है और कैसे यह मदद करता है
 – 
BDL
4 सितंबर 2020, 11:22
Sorting with recursive
function sort(arr){
const staticArr = [...arr]
  function recMaxSort(arrayARG,maxEL=0,resultArr = []){
    const [firstEl,...rest] = arrayARG;
    if (staticArr.length === resultArr.length){
      return resultArr
    }
    if (!firstEl){
      resultArr=[maxEL,...resultArr]
      const newArray = staticArr.filter(el=>{return !resultArr.includes(el)})
      return recMaxSort(newArray,0,resultArr)
    }

    if (maxEL>firstEl){
      return recMaxSort(rest,maxEL,resultArr)
    } else if (firstEl>=maxEL){
      return recMaxSort(rest,firstEl,resultArr)
    }

  }

  return  recMaxSort(arr)

}

 
 console.log(sort([231,4,7,3,54,500]));
-1
Quintis 14 जून 2020, 20:19
1
क्या आप कृपया कुछ स्पष्टीकरण जोड़ सकते हैं?
 – 
dan1st
4 सितंबर 2020, 10:29
नमस्कार ! आप वास्तव में क्या नहीं समझते हैं? मेरा कार्य सरणी विनाश पर आधारित है। जब रिकर्सन चालू होता है तो सरणी से सभी मानों की तुलना करें।
 – 
Quintis
5 सितंबर 2020, 18:33
मैंने सिर्फ इसलिए लिखा क्योंकि मुझे आपका जवाब एलक्यूपी समीक्षा कतार में मिला और आपने सिर्फ कोड लिखा और उसे समझाया नहीं।
 – 
dan1st
5 सितंबर 2020, 18:35