javascriptでのマージソートの簡単な実装

Question

マージソートアルゴリズムの実装後に何が問題になりますか。 は未定義を返します。

エラーは、マージ機能のどこかにあると思われます。

誰かが私にエラーを指摘するのに役立つことができます。

function mergeSort(arr1, lower, higher) { 

    if (lower < higher) { 
     var mid = Math.floor((lower + higher)/2); 
     mergeSort(arr1, lower, mid); 
     mergeSort(arr1, mid + 1, higher); 
     merge(arr1, lower, mid, higher); 
    } 
} 

マージ機能ここで

function merge(arr1, lower, mid, higher) { 

    var i = lower; 
    var j = mid + 1; 
    var k = 0; 
    var mergearr = []; 

    while (i < j && j <= higher) { 

     if (arr1[i] <= arr1[j]) { 
      mergearr[k] = arr1[i]; 
      k++; 
      i++; 
     } else { 
      mergearr[k] = arr1[j]; 
      k++; 
      j++; 
     } 

    } 

    if (i === j) { 
     while (j < higher) { 
      mergearr[k] = arr1[j]; 
      k++; 
      j++; 
     } 
    } else if (j > higher) { 
     while (i < j) { 
      mergearr[k] = arr1[i]; 
      k++; 
      i++; 
     } 
    } 


    for (var a = 0; a <= k; a++) { 
     console.log(a); 
     arr1[a] = mergearr[a]; 
     console.log(arr1[a]); 
    } 

    return arr1; 
} 

は、merge()機能があり、「オフ・バイ・1」の並べ替え中のエラーはさておき可能設定コンソール

index: 0 
value: 4 
index: 1 
value: 5 
index: 2 
value: 4 
index: 3 
value: undefined 
index: 0 
value: 4 
index: 1 
value: 4 
index: 2 
value: 5 
index: 3 
value: 4 
index: 4 
value: undefined 
index: 0 
value: undefined 
index: 1 
value: 4 
index: 2 
value: undefined 
index: 3 
value: undefined 
index: 0 

Answer 1

に出力されますマージされたリストを元の配列にコピーする方法での問題。この関数はlowerからhigherにマージするよう指示されます。しかし、マージされた配列は、インデックス0で始まる元の配列にコピーされます。代わりに、あなたは元の配列のみlowerとhigherの間で変更されていることを確認する必要があります。

for (var a = 0; a <= k; a++) { 
    console.log(a); 
    arr1[a + lower] = mergearr[a]; // <--- here 
    console.log(arr1[a + lower]); 
} 

Answer 2

私はあなたのコードを微調整することができます。はい、問題はmerge()の機能にありました。あなたはどこでも使用されていません。この値 以来merge()から何かを返す必要はありません

• ：見てみましょう。
• a書き換えないようにする ために毎にインクリメントされるlowerから開始する必要がありますが、すでに
はまた、あなたがインデックスを台無しに膨満奇妙な配列
• 奇数indexes`値を拾うためにあなたの建設の一部であったと をソート機能

var arr = [5,3,7,8,1,2,6,3,2]; 
 

 
mergeSort(arr, 0, arr.length - 1); 
 
console.log(arr); 
 

 
function mergeSort(arr, lower, higher) { 
 
    if (lower < higher) { 
 
     var mid = Math.floor((lower + higher)/2); 
 
     mergeSort(arr, lower, mid); 
 
     mergeSort(arr, mid + 1, higher); 
 
     merge(arr, lower, mid, higher); 
 
    } 
 
} 
 

 
function merge(arr, lower, mid, higher) { 
 
    var l = mid-lower+1, r = higher-mid, k = lower, mergearr = [], i = 0, j = 0; 
 

 
    while (i < l && j < r) { 
 
     if (arr[lower+i] <= arr[mid+j+1]) { 
 
      mergearr[k] = arr[lower+i]; i++; 
 
     } else { 
 
      mergearr[k] = arr[mid+j+1]; j++; 
 
     } 
 
     k++; 
 
    } 
 

 
    while (j < r) { 
 
     mergearr[k] = arr[mid+j+1]; k++; j++; 
 
    } 
 
    while (i < l) { 
 
     mergearr[k] = arr[lower+i]; k++; i++; 
 
    } 
 
    //console.log(mergearr, k, lower); 
 
    for (var a = lower; a < k; a++) { 
 
    arr[a] = mergearr[a]; 
 
    } 
 
}

の先頭に