Javascriptでのマージソートの反復アプローチ

Aug 23 2020

マージソートを繰り返し実装しようとしていますが、JavaScriptで実装しています。インターネットでも検索してみましたが、C、Python、Javaでしか検索できません。私の関数が与えている配列はソートされていません。別のことを試しましたが、エラーを理解できません。誰かが私が間違っていることを教えてもらえますか?

function mergeSortIterative(arr){
    let sorted=[...arr];//copying the array so that original remains unchanged.
    let n=sorted.length;
    let currSize;
    let leftStart;
    for(currSize=1;currSize<=n-1;currSize=2*currSize){
        for(leftStart=0;leftStart<n-1;leftStart+=2*currSize){
            let mid=Math.min(leftStart+currSize-1,n-1);
            let rightEnd=Math.min(leftStart+2*currSize-1,n-1);
            // let left=sorted.slice(leftStart,mid);
            // let right=sorted.slice(mid,rightEnd);
            // sorted=mergeIterative(sorted,left,right);
            mergeIterative(sorted,leftStart,mid,rightEnd);
        }
    }
    return sorted;
}

function mergeIterative(sorted,leftStart,mid,rightEnd){
    let left=sorted.slice(leftStart,mid);
    let right=sorted.slice(mid,rightEnd);
    let leftIndex=0,rightIndex=0,k=leftStart;
    while(leftIndex<left.length && rightIndex<right.length){
        //picking the lesser one 
        if(left[leftIndex]<=right[rightIndex]){
            sorted[k]=left[leftIndex];
            leftIndex++;
            k++;
        }
        else{
            sorted[k]=right[rightIndex];
            rightIndex++;
            k++;
        }
    }
    while(leftIndex<left.length && k<sorted.length){
        sorted[k]=left[leftIndex];
        leftIndex++;
        k++;
    }
    while(rightIndex<right.length && k<sorted.length){
        sorted[k]=right[rightIndex];
        rightIndex++;
        k++;
    }
}

回答

2 trincot Aug 23 2020 at 22:35

コードのエラーは、意味midrightEnd意味の定義に一貫性がありません。

次のコードから、これらのインデックスが前のサブ配列ののエントリを指していることがわかります。

let left = sorted.slice(leftStart, mid);
let right = sorted.slice(mid, rightEnd);

しかし、割り当てを見ると:

let mid = Math.min(leftStart + currSize - 1, n - 1); 
let rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);

...前のサブ配列の最後の要素を指していることがわかります。

これは2つの方法で修正できますが、slice引数を解釈する方法は「標準」の方法であるため、- 1次のように、割り当てを修正してすべてを削除することをお勧めします。

let mid = Math.min(leftStart + currSize, n); 
let rightEnd = Math.min(leftStart + 2 * currSize, n);
1 Omair Aug 23 2020 at 21:48

Pranav:Michael Laszloが以前に尋ねた同様の質問に対して提供した反復マージソートアルゴリズムを以下に引用しました:マージソートを反復的に実装する

function mergeSort(arr) {
  var sorted = arr.slice(),
      n = sorted.length,
      buffer = new Array(n);

  for (var size = 1; size < n; size *= 2) {
    for (var leftStart = 0; leftStart < n; leftStart += 2*size) {
      var left = leftStart,
          right = Math.min(left + size, n),
          leftLimit = right,
          rightLimit = Math.min(right + size, n),
          i = left;
      while (left < leftLimit && right < rightLimit) {
        if (sorted[left] <= sorted[right]) {
          buffer[i++] = sorted[left++];
        } else {
          buffer[i++] = sorted[right++];
        }
      }
      while (left < leftLimit) {
        buffer[i++] = sorted[left++];
      }
      while (right < rightLimit) {
        buffer[i++] = sorted[right++];
      }
    }
    var temp = sorted,
        sorted = buffer,
        buffer = temp;
  }

  return sorted;
}

function print(s) {
  document.write(s + '<br />');
}

var data = [1, 4, 10, 2, 9, 3];
print('input: ' + data.join(', '));
print('output: ' + mergeSort(data).join(', '));