JavaScriptによるマージソートを理解する

投稿日: 2022-04-20 2022-10-08
タグ: javascript

以前は、初心者の並べ替えアルゴリズムのいくつかについて説明しました。これらのアルゴリズムは、仕事をこなすことができますが、より大きなデータセットではすぐに手に負えなくなります。これで、マージソートなどのより効率的なビッグボーイアルゴリズムのいくつかを掘り下げ始めることができます。これで、私たちはから移動することができます O(n^2) はるかにスケーラブルなアルゴリズム O(nlogn) 解決。

前提条件

Big O Notation を介して時間と空間の複雑さについて考えることができると、非常に役立ちます。また、再帰ベースの例も検討するので、ここでをブラッシュアップできます。

コンセプト

二分探索と同様に、マージソートは分割統治アルゴリズムです。目標は、問題をサブ問題に分解し、簡単に元に戻すことができる単純な問題がたくさんあるまで、それらを再帰的に分解し続けることです。

マージソートは、個々のアイテムではなく配列全体を比較するという考えに基づいて構築されています。まず、配列全体を取得し、すべてが独自の配列に単独で存在するようになるまで、すべてを継続的に半分に分割して、配列を多くのサブ配列に分割する必要があります。サブ配列の数はメイン配列のアイテム数の数倍になるので、それがログインになります O(nlogn).

そこからマージを開始できます。両方の配列はすでに並べ替えられているはずなので、それぞれの数値が小さい方を簡単に比較して、適切な場所に配置できます。これは、 O(nlogn) から来た。

ご覧のとおり、配列の半分は後半の前に完了し、それぞれの前半は次の半分の前に完了します（異なる色は異なる配列を表します）。

VisuAlgo.netのおかげでグラフィック/アニメーション

練習データ

これが私が参照する50の分類されていないアイテムの配列です。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

マージ

問題を単純化するために、2つのソートされた配列をマージするユーティリティ関数を作成することから始めることができます。これを行うにはさまざまな方法がありますが、これが最も簡潔であることがわかりました。

いずれかの配列にアイテムがある限り、いずれかの配列の最初のアイテムが小さいかどうかを確認し、それを並べ替えにスローして、そのアイテムを配列から削除します。 shift(). それが終わったら、1つの配列が大きい場合など、何かが残っている場合は、それを最後に連結します。

したがって、両方の配列は、すでにソートされているため、一方が空になり、残りが最後にスローされるまで、徐々に縮小します。

const merge = (arr1, arr2) => {
  let sorted = [];

  while (arr1.length && arr2.length) {
    if (arr1[0] < arr2[0]) sorted.push(arr1.shift());
    else sorted.push(arr2.shift());
  };

  return sorted.concat(arr1.slice().concat(arr2.slice()));
};

console.log(merge([2, 5, 10, 57], [9, 12, 13]));

並べ替え

これは簡単な部分です。再帰関数を使用して、配列を連続的に半分にカットできます。 slice() 中央の両側にデータを保存します。 1つのアイテムの配列があると返され、次に merge それらを1つの大きな配列に戻し、マージするたびにそれらを途中でソートするユーティリティ。

const mergeSort = arr => {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2),
      left = mergeSort(arr.slice(0, mid)),
      right = mergeSort(arr.slice(mid));

  return merge(left, right); 
};

console.log(mergeSort(unsortedArr));

結論

マージソートは、これまでカバーしてきた中で最高のアルゴリズムです。 O(nlogn)、大量のデータでより適切に機能することを覚えておくとよいでしょう。並べ替える必要のあるデータの量がわからない場合は、データセットが両方の長所を最大限に活用できるほど小さい場合は、挿入並べ替えなどの別のアルゴリズムを使用することを検討してください。

getdocs

13036