1. 概要

このチュートリアルでは、反復アルゴリズムを使用してマージソートアルゴリズムを実装する方法について説明します。 まず、マージソートアルゴリズムとその再帰バージョンについて説明します。

その後、このアルゴリズムの反復アプローチについて説明します。 また、アイデアを明確にするための簡単な例を示します。

最後に、反復アルゴリズムと再帰アルゴリズムの比較と、それぞれをいつ使用するかを示します。

2. マージソートアルゴリズム

ご存知のように、マージソートアルゴリズムは効率的なソートアルゴリズムであり、時間計算量内で配列をソートできます。ここで、は値の数です。

通常、再帰的アプローチがより普及していることがわかります。 したがって、再帰アルゴリズムの手順をすばやく覚えて、後で反復アルゴリズムを理解しやすくしましょう。 再帰バージョンは、除算と征服戦略に基づいています。

  • 除算：このステップでは、入力を2つに分割します。ピボットは配列の中点です。 このステップは、分割する半分がなくなるまで、すべての半分の配列に対して再帰的に実行されます。
  • 征服：このステップでは、分割されたパーツを下から上に並べ替えてマージし、完全な並べ替え結果を取得します。

3. 反復アプローチ

3.1. 一般的なアイデア

再帰バージョンで示したように、入力を2つに分割しました。 このプロセスは、配列の各要素だけを取得するまで続きました。 次に、並べ替えられたすべての値を含む完全な結果が得られるまで、並べ替えられた部分を下から上にマージしました。

いつものように、再帰バージョンから反復バージョンに移行することを考えようとしているときは、再帰の反対の方法で考える必要があります。 反復アプローチの実装に役立ついくつかの考えをリストしてみましょう。

  1. 配列の各要素をソートされた部分と見なします。 まず、この部分には単一の値が含まれています。
  2. 2番目のステップでは、2つの隣接する要素ごとにマージして、ソートされたパーツを取得します。 最初は、各部分に2つの値があります。 ただし、パーツの数が奇数の場合、最後のパーツには2つ未満の値が含まれる可能性があります。
  3. パーツのサイズがアレイ全体に達するまで、手順1と2を実行し続けます。 それまでに、結果はソートされていると言えます。

これで、実装に飛び込むことができます。 ただし、アルゴリズムを単純化するために、最初に2つの隣接する部分のマージを担当する関数を実装します。 その後、マージ関数に基づいて完全なアルゴリズムを実装する方法を説明します。

3.2. マージ機能

2つのソートされた部分をマージし、最初と2番目の部分のすべての要素を含むマージされたソートされた配列を返す単純な関数を実装しましょう。 実装を見てください：

マージ関数では、3つのループを使用します。 1つ目は、2つの部分を一緒に繰り返すことです。 各ステップで、両方の部分から小さい方の値を取得し、最終的な答えを保持する配列内に格納します。

結果に値を追加したら、一歩前進します。 変数は、に追加される次の値を保持する必要があるインデックスを指します。

2番目のループでは、最初の部分の残りの要素を繰り返し処理します。 各値はに格納されます。 3番目のループでは、2番目のループと同様の操作を実行します。 ただし、ここでは、2番目の部分の残りの要素を繰り返し処理します。

2番目と3番目のループは、最初のループが終了した後、パーツの1つに要素が残っている可能性があるためです。 これらの値はすべて追加された値よりも大きいため、結果の回答に追加する必要があります。

マージ関数の複雑さはです。ここで、は最初の部分の長さであり、は2番目の部分の長さです。

この関数の複雑さは、渡される部分の長さに関して線形であることに注意してください。 ただし、配列のごく一部を処理するために関数を呼び出す可能性があるため、配列全体と比較して線形ではありません。

3.3. マージソート

次に、マージ関数を使用して、マージソートの反復アプローチを実装しましょう。 実装を見てください：

まず、このステップでアルゴリズムが処理する各パーツのサイズを示すところから始めます。

各ステップで、サイズのすべての部分を反復処理し、隣接する2つの部分のそれぞれの開始と終了を計算しました。 両方の部分を決定したら、アルゴリズム1で定義された関数を使用してそれらをマージしました。

2つの特殊なケースを処理したことに注意してください。 1つ目はアレイの外側に到達した場合で、2つ目は外側に到達した場合です。 これらの場合の理由は、最後の部分に含まれる要素が少ない可能性があるためです。 したがって、を超えないようにサイズを調整します。

マージが終了した後、要素をからのそれぞれの場所にコピーします。

各ステップで、単一のパーツの長さを2倍にしたことに注意してください。 その理由は、長さの2つの部分をマージしたためです。 したがって、次のステップでは、サイズのすべての部分がソートされていることがわかります。

最後に、ソートされたを返します。

反復アプローチの複雑さはです。ここで、は配列の長さです。 その理由は、最初のループでは、各ステップの値を2倍にするためです。 だから、これはです。 また、各ステップで、配列内の各要素を2回繰り返し、合計で完全な配列の関数を呼び出します。 したがって、これはです。

4. 例

反復バージョンをより明確に理解するために例を見てみましょう。 次のような配列があるとします。

反復アルゴリズムをに適用してみましょう。

最初のステップでは、要素を要素とマージします。 その結果、最初の2つの値を含む新しいソート済みパーツが取得されます。 はよりも小さいので、両方を交換します。

同様に、and要素に対してこの操作を実行します。 ただし、この場合、それらはすでにソートされており、順序は維持されます。 および値についてもこの操作を続行します。

これらの手順の後、サイズ2のパーツが次のように並べ替えられます。

2番目のステップでは、は2になります。 したがって、3つの部分があります。 これらの各パーツには、2つの要素が含まれています。 前の手順と同様に、最初の部分と2番目の部分をマージする必要があります。 したがって、最初の4つの値を含む新しいパーツを取得します。 3番目の部分については、前の手順で並べ替えられたためスキップします。4番目の部分とのマージはありません。

次の手順を実行した後の結果を確認してください。

最後のステップで、は4になり、2つの部分があります。 最初の要素には4つの要素が含まれ、2番目の要素には2つの要素が含まれます。 これらのパーツのマージ関数を呼び出します。

マージが終了すると、最終的にソートされた回答が得られます。

5. 比較

いつものように、再帰はコードのサイズを減らし、考えて実装するのが簡単になります。 一方、実行が遅いスタックメモリを使用するため、より多くのメモリを消費します。

そのためには、速度とメモリの節約のために反復アルゴリズムを使用することをお勧めします。 ただし、たとえば、小さな配列があるかのように実行時間とメモリを気にしない場合は、再帰バージョンを使用できます。

6. 結論

このチュートリアルでは、反復アプローチを使用してマージソートアルゴリズムを実装する方法を説明しました。 最初に、アルゴリズムの再帰バージョンを使用したマージソートアルゴリズムについて説明しました。

次に、このアルゴリズムの反復バージョンについて説明しました。 また、その複雑さの背後にある理由を説明しました。

その後、アイデアを明確にするための簡単な例を示しました。

最後に、反復アルゴリズムと再帰アルゴリズムの比較を示し、それぞれを使用するためのベストプラクティスを示しました。