[JavaScript] Merge Sort

5869 ワード
Merge sort 連結ソート 2021.8.9（月） アルゴリズム#アルゴリズム# テキストリンク

連結ソート(Merge Sort)



マージソートは、配列を半ソートと再マージを繰り返すソートアルゴリズムです.連結ソートは通常、2つの関数で構成されます.
この関数は次のようになります.
1.グループ化された配列を1つにまとめる関数
function merge(left, right){
  const result = [];
  while(left.length > 0 && right.length > 0){
    if(left[0] <= right[0]) {
      result.push(left.shift());
    }
    else if(left[0] > right[0]) {
      result.push(right.shift());
    }
  }
  return [...result, ...left, ... right];
}
この関数は半分に分けられ,伝達されたパラメータを比較して並べ替えられる.
2.配列を半分に分け、左、右のパラメータをmerge関数の関数に渡す
function mergeSort(arr) {
  if(arr.length === 1) return arr;
  const middleIdx = Math.floor(arr.length / 2);
  const left = arr.slice(0, middleIdx);
  const right = arr.slice(middleIdx);
  return merge(mergeSort(left), mergeSort(right));
この関数は、配列長が1になるまで再帰的に繰り返し、merge関数に左および右に渡されます.その後、左側と右側の配列を比較することで、マージプロセスを繰り返し、最終的に整列した配列を作成できます.
[接続リスト]コンセプト-1
[TIL #26] Code Kata