【図解】マージソート:アルゴリズム【C言語】

本記事では、基本的なソートの一種である「マージソート」のアルゴリズム解説・C言語による実装を確認していきます。

 

アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています

 

ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。

 

 

 本記事でわかること

  • マージソートの基本的な情報
  • アルゴリズムの流れ
  • C言語による実装方法

 

 

こちらの記事で、他のソートアルゴリズムをまとめています。

>>ソートアルゴリズム 計算量・特徴一覧

 

 

アルゴリズム入門書はこの一冊で十分!

 

 

 

マージソートとは

マージソートは、ソートアルゴリズムの一種であり、クイックソートと同様、分割統治法を用いてソートを行うアルゴリズムです。

>>【図解】クイックソート:アルゴリズム【C言語】

 

ちなみに、分割統治法とは、「大きな問題をそのまま解くのではなく、小さな問題に分割して、それぞれを解くことで、最終的に大きな問題を解く方法」のことを言います。

 

 

マージソートの基本的な情報は以下になります。

 

最悪計算時間 \(O\) 安定性
\(O(nlog(n))\) 安定

 

マージソートの計算時間は、\(O(nlog(n))\)であるため、ソートの中では高速に動作する部類です。

 

その一方、複数の配列を必要とするため、メモリを多く使うという難点があります。

 

では、次の章から、実際のマージソートのアルゴリズムを見ていきましょう。

 

 

スポンサーリンク

 

マージソートのアルゴリズム

まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。

 

マージソートのアルゴリズムは以下のようになります。

 

配列全体に対してmergeSortを行う

 

mergeSortでは以下の処理を行う

  1. 対象の配列を二分割し、それぞれ別の配列にコピーする
  2. 二分割したそれぞれの配列に対し、mergeSortを行う
  3. 二分割した配列を統合(merge)する

 

mergeSortの処理の中で、さらにmergeSortを行うため、これは再帰的な処理になります。

 

文面だとよくわからないと思うので、さっそく実例を見ていきましょう。

 

 

では、サイズが8の配列で昇順ソートの具体例を見ていきます。

 

ここでは、配列の初期状態を次のようにします。

 

まずは、この配列全体に対してmergeSortを適用します。

 

mergeSortでは、最初に配列を二分割しますね。

 

二分割の仕方は、単純に中央から左右に分けるだけです。

 

この際、left、mid、rightという変数を使い、以下の図のように添え字を設定します。

 

 

3つの変数の役割を説明しますね。

 

left:対象の配列の先頭位置を指し示す変数

right:対象の配列の末尾の1つ後ろを指し示す変数

mid:leftとrightの中央の位置を指し示す変数

 

midは、 mid = (left + right) / 2  で求めることができます。

 

配列を二分割するために、これら3つの変数を使います。

 

具体的には、leftからmidの手前まで、midからrightの手前まで、という風に表すことで配列を二分割します。

 

 

では、上の図のように分け、配列の中身を2つの配列へとコピーしていきましょう。

この時、これら2つの配列は新たに生成したものになります。

 

 

では、2つに分割した配列それぞれに対して、再びmergeSortを適用します。

 

新たに生成した2つの配列でのleft、mid、rightはこのようになりますね。

 

 

では、先ほどと同様に、leftからmidの手前まで、midからrightの手前までで二分割します。

 

実際のプログラムでは再帰的な処理をするため、左側を優先的分割していきますが、ここでは便宜上2つの配列を同時に処理します。

 

まず、左側の配列は次のように分割されます。

 

 

そして、右側の配列は次のように分割されます。

 

 

分割後の配列の要素数が1つ以下になるまで、分割処理を繰り返します。

 

今回の例だと、まだすべての配列の要素数が2つあるので、もう一度2つに分割していきます。

 

 

 

これで、分割後の要素数がすべて1以下になったので、分割処理を終了します。

 

全体図を確認すると、現時点では、このように元の配列を分割していることになります。

 

 

ちなみに、マージソートでは、これらの配列すべてを記憶しておく必要があるため、メモリを多めに使うことになります

冒頭付近で欠点として挙げたことですね。

 

 

では、ここからはマージ(統合)の処理に移ります。

 

マージの概要を簡単に確認しておきましょう。

 

  1. 分割した2つの配列の先頭要素から順番に大小を比較する
  2. 小さい方の値を、分割前の配列へ、先頭から順番に置き換える

 

 

では、1番下の段から見ていきましょう。

ここですね。

 

 

分割された2つの配列の要素を、先頭から順番に比較していきます。

とりあえず、「最小値を選びたい」というモチベーションです。

 

この場合だと、「4」と「2」を比較、「8」と「1」を比較、、、といった感じです。

 

比較した後、小さい方の値を、分割前の配列へと、先頭から順番に上書きしていきます。

 

 

分割後の配列のすべての要素を上書きに使用するまで、この処理を繰り返します。

 

上の例だと、例えば、「4」と「2」のうち「2」を上書きに使用したため、残った「4」が自動的に元の配列へと上書きされます。

 

 

これでマージの処理が1セット終わりました。

 

次は、もう1段上を見に行きます。

 

ここですね。

 

 

先程の処理によって、要素の並び方が変わっていることが確認できます。

別の言い方をすると、「小さな配列のそれぞれがソート済みである」ということです。

 

少し話は脱線しますが、分割前の配列も同様の並びとなっているのは、配列が参照渡しであることが要因です。

つまり、この段階では、もともとのサイズ8の配列も、「2 4 1 8 3 7 6 9」のように並び変わっているということです。

 

参照渡しについては、こちらで説明しています。

>>【プログラミング】 値渡し・参照渡しの違い

 

 

話を戻します。

では、その小さい配列の要素を、それぞれ先頭から比較していきましょう。

 

ちなみに、先頭から比較していく理由は、下の段がすでにソート済みであるため、先頭を比較するだけで最小値が確定するからです。

 

 

では、同様の処理を繰り返していきます。

 

 

残りも同じようにして、小さい方の値から順番に、分割前の配列へと代入していきます。

 

この段は最終的に、以下のようになります。

 

 

では、最後に一番上の段を見ていきます。

 

最後はこのようになっていますね。

 

 

上の方でも確認したように、分割前の配列も、小さな配列の並び替えが適用されています。

 

では、これら2つをマージしていきます。

 

 

最後にもう一度だけ確認します。

 

 

これを繰り返すことで、最終的に、以下のようになります。

 

 

これで、もともとの配列を昇順に並び替えることができました。

 

ここまでが、マージソートの流れになります。

 

次の章では、これをC言語で実装していきます。

実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。

 

スポンサーリンク

 

マージソートの実装【C言語】

さっそく、プログラム全体のコードを示します。

 

 

配列を二分割していく処理は、42~50行目の mergeSort 関数の中で行っています。

 

見てもらうとわかるように、 mergeSort は再帰関数です。

 

マージ(統合)していく処理は、16~39行目の merge 関数の中で行っています。

 

コメントをなるべく多めに入れているので、前の章で確認したアルゴリズムと照らし合わせながら、コードを読み解いてみてください。

 

では、今回はここまでとします。

お疲れさまでした。

 

別のソートを確認したい方は、ソートアルゴリズム 計算量・特徴一覧をご覧ください。