जावास्क्रिप्ट मर्ज सॉर्ट और रिकर्सन

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

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

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

मर्ज सॉर्ट में, हम सरणी को छोटे सरणी में विभाजित कर रहे हैं जब तक कि इसका आकार 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]))

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]));