C++でマージソートを実装してみる
今まで初等的なソートアルゴリズムである挿入ソート、バブルソート、選択ソートを実装してきました。
しかし、これらは簡単に実装できるものの、遅いです。そこで、今度はより高速なソートアルゴリズムを実装してみたいと思います。今回はマージソートです。
目標
マージソートを実装できるようになる。
マージソート
マージソートは分割統治法を利用した高速なソートアルゴリズムです。分割統治法とは、問題を分割(devide)して部分問題を解いて(solve)から、それらを統合(conquer)して解を得る手法の総称です。
マージソートでは、配列をどんどん2つに分割していき、1要素ごとにまで分解してから、ソートしながら統合します。
アルゴリズム
- 配列を1つの要素づつの配列に分解する(devide)。
- 以下を繰り返す:
- 隣り合う2つの部分列から、要素を小さい順に取り出して並べ、配列に格納する(solve & conquer)。
- 統合してできたソート済みの新たな配列を部分列とする。これは次の統合に使用される。
上の図の統合部分を木構造と見ると、階層の数は(より)。統合に利用する2つの部分列の要素数をそれぞれn1、n2とすると、1回の統合につき計算量はn1+n2なので1階層の統合につき計算量は。したがって、マージソートの計算量はとなります。バブルソート()などの初等的ソートアルゴリズムに比べてだいぶ速いことがわかります。
実装してみる
順を追って実装していきます。まずはマージソートを行う関数merge_sortを定義します。再帰関数を利用します。
部分列の範囲を指定するのに変数left、rightを使用しています。それぞれ部分列の先頭、末尾+1の要素を指し、left、rightを移動することで配列の分割を表現します。要素が1つの場合(left+1 = right)は何もせず、そうでない場合は2つの部分列に分けて再帰的に自分自身を呼び出しています。
void merge_sort(int A[], int left, int right) { if (left + 1 < right) { int mid; mid = (left + right) / 2; // devide merge_sort(A, left, mid); merge_sort(A, mid, right); // conquer merge(A, left, mid, right); } }
次に2つの部分列を統合する関数mergeを実装します。ここで注意してほしいのは、部分列R、Lの最後に定数INFTYを格納することで要素数がそれぞれn1+1、n2+1となっていることです。INFTYには、配列に格納されている全ての値より大きな値を指定します。統合の際に要素の大きさを比較していますが、末尾をINFTYとすることにより、ここの実装が簡単になります。片方の部分列の要素が統合先に全て格納されたとき、もう片方の部分列の要素がINFTYと比較され統合先に順々に格納されるることになるからです。
void merge(int A[], int left, int mid, int right) { int i, j, k; int n1, n2; // 部分列L, Rの要素数決定に利用 n1 = mid - left; n2 = right - mid; int L[n1+1], R[n2+1]; for (i = 0; i < n1; i++) L[i] = A[left + i]; for (i = 0; i < n2; i++) R[i] = A[mid + i]; L[n1] = INFTY; R[n2] = INFTY; // sort j = 0; k = 0; for (i = left; i < right; i++) { if (L[j] <= R[k]) { A[i] = L[j]; j++; } else { A[i] = R[k]; k++; } } }
問題を解いてみる
上で実装した関数を利用して、Aizu Online Judgeの問題を解きます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B
#include<iostream> using namespace std; #define INFTY 1000000001 int cnt = 0; void merge(int A[], int left, int mid, int right) { int i, j, k; int n1, n2; // 部分列L, Rの要素数決定に利用 n1 = mid - left; n2 = right - mid; int L[n1+1], R[n2+1]; for (i = 0; i < n1; i++) L[i] = A[left + i]; for (i = 0; i < n2; i++) R[i] = A[mid + i]; L[n1] = INFTY; R[n2] = INFTY; // sort j = 0; k = 0; for (i = left; i < right; i++) { if (L[j] <= R[k]) { A[i] = L[j]; j++; } else { A[i] = R[k]; k++; } } } void merge_sort(int A[], int left, int right) { if (left + 1 < right) { int mid; mid = (left + right) / 2; // devide merge_sort(A, left, mid); merge_sort(A, mid, right); // conquer merge(A, left, mid, right); } } int main() { int i, n, S[500000]; cin >> n; for (i = 0; i < n; i++) cin >> S[i]; merge_sort(S, 0, n); for (i = 0; i < n; i++) { if (i > 0) cout << " "; cout << S[i]; } cout << endl; cout << cnt << endl; return 0; }
参考
渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.