私たちは基本的なソートアルゴリズムで行われます!バブルソート、選択の並べ替えと挿入の並べ替えを簡単に理解し、あなたの頭を包む.それらを実装することは自然に時間とともに来るでしょう.真実は、これらの基本的なアルゴリズムは、彼らの欠点があると言われる-彼らはよくスケールしないでください!入力のサイズを2倍にすると、ソートされた配列を生成する時間が2倍になります!
このように、私たちはソート時間がo(Nlog(n))であるいくつかのより高度なアルゴリズムに移ります.それ以上のADOなしでこれらの効率的なJavaScriptのソートアルゴリズム-マージソートの最初を紹介しましょう.

マージソート入門

マージソートは、我々が見たソートアルゴリズムに比べて全く異なっている.マージソートは、開始配列を0または1の要素の小さな配列に分割し、それらを一緒に戻します.配列を2回ループする必要はありません!
全体のプロセスには2つの大きなステップがあります.
アレイを分割する

は、より小さな配列を一緒にバック

を合併する

可視化

このアルゴリズムの入力は[38, 1, 40, 34, 9, 41, 2, 16]です.📊

マージソートの可視化Visualgoを使用します.どうぞご覧下さいhttps://visualgo.net/より多くの視覚的アルゴリズム.
非常に多くの仕事権利のようです?しかし、それはちょうど配列(色の要素)を分割して、それから要素をまとめることです.まず、マージロジックを理解しましょう.アルゴリズムの1ポイントで、以下のサブアレイ- [[1, 38], [34, 40]]をマージしなければなりませんでした.それらの両方はソートされます-これらの2つのサブアレイで見つかるすべての要素を含む新しいソートされた配列を生産するために、それは要件です.

マージ実装

マージソート用の擬似コードです.

空の配列を作成し、インデックスiとjを作成する

私たちがAT 1を見ていない値がまだある間.最初の配列の値が2番目の配列の値より小さい場合は、その値を空の配列にプッシュし、Iの値を増やし、最初のArray2で次の値に移動します.さもなければ、2番目の配列の値が最初の配列の値より小さい場合、私たちは、その値を空の配列にプッシュし、Jの値をインクリメントし、2番目の配列

の次の値に移動します

、1つの配列からのすべての要素がソートされた配列にプッシュされると、すべての残りの要素を2番目の配列からソートされた配列にプッシュします

function merge(arr1, arr2) {
  let results = [];

  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  console.log(results);
  return results;
}

ここで何が起こっているかを見るためにコードを使いましょう.ループを実行する前に、空の配列と2つのインデックスを作成しました.ループは、インデックスIとJの値をチェックします.arr 1のインデックスiの要素がarr 2のインデックスjの要素より小さい場合、その要素を結果配列にプッシュします.
我々の代表的な配列を考慮に入れて、我々はインデックス0と0で値を比較します、そして、それは1と34であるので、我々は結果配列に1を押して、iの値を増やします.次の繰り返しは我々が現在38と34である1と0でインデックスを比較します、そして、34を考慮すると、我々は34を結果として配列に押し付けます(現在は[ 1 , 34 ].そして、我々は最終的にソートされる完成した配列があるまで、これを繰り返し続けます.

マージソート実装

念頭に置いてください:このソリューションはrecursionを使用します.再帰的なコードを使ったことのないプログラマは、再帰的な再帰を見つけることができるかもしれません.また、概念を理解するためのリンクをチェックするのは良い考えかもしれません.
マージソート用の擬似コードは次のとおりです.

アルゴリズムは、要素を含まない配列を生成するか、または1つの要素

のみを生成するまで、配列を停止し続ける

これらの配列が存在すると、アルゴリズムはこれらの配列(上記のメソッドを使用して)をマージします.

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

ベースは、配列の長さが1かゼロであるとすぐに、配列を返します.さもなければ、私たちは中央の要素を分解し、配列を2つのサブアレイに分割し、最後に、それらの2つの配列にマージを呼び出します.
現在、我々は視覚化を見ます.
便利に、私たちの配列に8つの要素があります.アルゴリズムは最初に配列を4に分割し、次に2に、そして1つの要素サブアレイに分割する.つのポイントで、要素はすべて異なる色です-それは、彼らが個人であることを意味します.次に、アルゴリズムは、一緒に戻って要素をマージ開始します- 38と1は[ 1 , 38 ]になります、40と34は[ 34 , 40 ]になります、そして、これらの2つの配列は合併されます、そして、すべての要素がソートされるまで、アルゴリズムは走ります.

ビッグO複雑性

最良のケース、平均ケース、およびマージソートの最悪のケースはすべて同じです- o ( nlog ( n )).log ( n )は、アルゴリズムが作成しなければならない除算の数から来る.8つの要素を持つことは、配列を3回半分にする必要があることを意味します.

最初に、4つの要素を持つ2つの配列をそれぞれ得る

二度目の2つの要素を持つ4つの配列を得る

三度目の1つの要素を持つ8つの配列を取得します
入力配列のサイズを2倍にすると、アルゴリズムに1つの除算を追加する必要があります.式のnは、配列が一緒に戻ってマージされたときの比較の数から来ます.

結論

そして、それはマージソートで私たちの4番目のJavascriptのソートアルゴリズムの記事です!基本的な3つよりも少し包括的な、しかしまだ理解しやすい、右?あなたがこのシリーズが好きであるならば、全部のシリーズをチェックしてください、さもなければ、より多くの技術記事のために私のblogを訪問してください.