本記事では、基本的なソートの一種である「マージソート」のアルゴリズム解説・C言語による実装を確認していきます。
アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。
ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。
- マージソートの基本的な情報
- アルゴリズムの流れ
- C言語による実装方法
こちらの記事で、他のソートアルゴリズムをまとめています。
アルゴリズム入門書はこの一冊で十分！
マージソートとは
マージソートは、ソートアルゴリズムの一種であり、クイックソートと同様、分割統治法を用いてソートを行うアルゴリズムです。
ちなみに、分割統治法とは、「大きな問題をそのまま解くのではなく、小さな問題に分割して、それぞれを解くことで、最終的に大きな問題を解く方法」のことを言います。
マージソートの基本的な情報は以下になります。
| 最悪計算時間 \(O\) | 安定性 |
| \(O(nlog(n))\) | 安定 |
マージソートの計算時間は、\(O(nlog(n))\)であるため、ソートの中では高速に動作する部類です。
その一方、複数の配列を必要とするため、メモリを多く使うという難点があります。
では、次の章から、実際のマージソートのアルゴリズムを見ていきましょう。
マージソートのアルゴリズム
まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。
マージソートのアルゴリズムは以下のようになります。
配列全体に対してmergeSortを行う
mergeSortでは以下の処理を行う
- 対象の配列を二分割し、それぞれ別の配列にコピーする
- 二分割したそれぞれの配列に対し、mergeSortを行う
- 二分割した配列を統合（merge）する
mergeSortの処理の中で、さらにmergeSortを行うため、これは再帰的な処理になります。
文面だとよくわからないと思うので、さっそく実例を見ていきましょう。
では、サイズが８の配列で昇順ソートの具体例を見ていきます。
ここでは、配列の初期状態を次のようにします。
まずは、この配列全体に対してmergeSortを適用します。
mergeSortでは、最初に配列を二分割しますね。
二分割の仕方は、単純に中央から左右に分けるだけです。
この際、left、mid、rightという変数を使い、以下の図のように添え字を設定します。
3つの変数の役割を説明しますね。
left：対象の配列の先頭位置を指し示す変数
right：対象の配列の末尾の1つ後ろを指し示す変数
mid：leftとrightの中央の位置を指し示す変数
midは、 mid = (left + right) / 2 で求めることができます。
配列を二分割するために、これら３つの変数を使います。
具体的には、leftからmidの手前まで、midからrightの手前まで、という風に表すことで配列を二分割します。
では、上の図のように分け、配列の中身を２つの配列へとコピーしていきましょう。
この時、これら２つの配列は新たに生成したものになります。
では、2つに分割した配列それぞれに対して、再びmergeSortを適用します。
新たに生成した２つの配列でのleft、mid、rightはこのようになりますね。
では、先ほどと同様に、leftからmidの手前まで、midからrightの手前までで二分割します。
実際のプログラムでは再帰的な処理をするため、左側を優先的分割していきますが、ここでは便宜上２つの配列を同時に処理します。
まず、左側の配列は次のように分割されます。
そして、右側の配列は次のように分割されます。
分割後の配列の要素数が１つ以下になるまで、分割処理を繰り返します。
今回の例だと、まだすべての配列の要素数が２つあるので、もう一度２つに分割していきます。
これで、分割後の要素数がすべて１以下になったので、分割処理を終了します。
全体図を確認すると、現時点では、このように元の配列を分割していることになります。
ちなみに、マージソートでは、これらの配列すべてを記憶しておく必要があるため、メモリを多めに使うことになります。
冒頭付近で欠点として挙げたことですね。
では、ここからはマージ（統合）の処理に移ります。
マージの概要を簡単に確認しておきましょう。
- 分割した２つの配列の先頭要素から順番に大小を比較する
- 小さい方の値を、分割前の配列へ、先頭から順番に置き換える
では、１番下の段から見ていきましょう。
ここですね。
分割された２つの配列の要素を、先頭から順番に比較していきます。
とりあえず、「最小値を選びたい」というモチベーションです。
この場合だと、「４」と「２」を比較、「８」と「１」を比較、、、といった感じです。
比較した後、小さい方の値を、分割前の配列へと、先頭から順番に上書きしていきます。
分割後の配列のすべての要素を上書きに使用するまで、この処理を繰り返します。
上の例だと、例えば、「４」と「２」のうち「２」を上書きに使用したため、残った「４」が自動的に元の配列へと上書きされます。
これでマージの処理が１セット終わりました。
次は、もう１段上を見に行きます。
ここですね。
先程の処理によって、要素の並び方が変わっていることが確認できます。
別の言い方をすると、「小さな配列のそれぞれがソート済みである」ということです。
少し話は脱線しますが、分割前の配列も同様の並びとなっているのは、配列が参照渡しであることが要因です。
つまり、この段階では、もともとのサイズ８の配列も、「２ ４ １ ８ ３ ７ ６ ９」のように並び変わっているということです。
参照渡しについては、こちらで説明しています。
話を戻します。
では、その小さい配列の要素を、それぞれ先頭から比較していきましょう。
ちなみに、先頭から比較していく理由は、下の段がすでにソート済みであるため、先頭を比較するだけで最小値が確定するからです。
では、同様の処理を繰り返していきます。
残りも同じようにして、小さい方の値から順番に、分割前の配列へと代入していきます。
この段は最終的に、以下のようになります。
では、最後に一番上の段を見ていきます。
最後はこのようになっていますね。
上の方でも確認したように、分割前の配列も、小さな配列の並び替えが適用されています。
では、これら２つをマージしていきます。
最後にもう一度だけ確認します。
これを繰り返すことで、最終的に、以下のようになります。
これで、もともとの配列を昇順に並び替えることができました。
ここまでが、マージソートの流れになります。
次の章では、これをC言語で実装していきます。
実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。
マージソートの実装【C言語】
さっそく、プログラム全体のコードを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <stdio.h> #define N 8 // 配列の全ての要素を出力する void printArray(int A[], int n) { for (int i = 0; i < n; i++) if (i == 0) printf("%d", A[i]); else printf(" %d", A[i]); printf("\n"); } // 配列をマージ（統合）する関数 void merge(int A[], int left, int mid, int right) { int n1 = mid - left; // 左側の配列の要素数 int n2 = right - mid; // 右側の配列の要素数 int L[n1], R[n2]; // 分割した配列をコピーする配列 int i, j, k; // 対象の配列を二分割する for (i = 0; i < n1; i++) L[i] = A[left + i]; for (i = 0; i < n2; i++) R[i] = A[mid + i]; // 2つの配列の添え字を初期化 i = 0, j = 0; // ２つの配列から最小値を元の配列へと代入していく for (k = left; k < right; k++) { // 小さい値から順番に、元の配列へと代入する if (L[i] <= R[j] && i < n1) A[k] = L[i++]; else A[k] = R[j++]; } } // マージソート void mergeSort(int A[], int left, int right) { // 分割した配列の要素数が1個以下になるまで繰り返す if (left+1 < right) { int mid = (left + right) / 2; mergeSort(A, left, mid); // 右側の配列にmergeSortを適用する mergeSort(A, mid, right); // 右側の配列にmergeSortを適用する merge(A, left, mid, right); // マージを行う } } int main(void) { int A[N] = {4, 2, 8, 1, 7, 3, 9, 6}; printArray(A, N); mergeSort(A, 0, N); // マージソートを行う printArray(A, N); return 0; } |
配列を二分割していく処理は、42~50行目の mergeSort 関数の中で行っています。
見てもらうとわかるように、 mergeSort は再帰関数です。
マージ（統合）していく処理は、16~39行目の merge 関数の中で行っています。
コメントをなるべく多めに入れているので、前の章で確認したアルゴリズムと照らし合わせながら、コードを読み解いてみてください。
では、今回はここまでとします。
お疲れさまでした。
別のソートを確認したい方は、ソートアルゴリズム 計算量・特徴一覧をご覧ください。