マージソート Merge Sort

マージソートは、高速でかつ安定なソートアルゴリズムです。しかも、効率はやや劣りますが、クイックソートと比べると実装が簡単で理解もし易いアルゴリズムです。高速で安定という特徴から、様々なところで実用されています。

マージソートのアルゴリズムは分割統治法を応用します。そして、マージソートは分割統治法を説明するための最も良い例ともなるので、分割統治法のアイデアもついでに知ることができます。下図は、マージソートの流れを表しています。

ステップ1	配列による入力データ
ステップ2	配列を２つに分割する
ステップ3	分割された部分配列をさらに分割する
ステップ4	分割された部分配列をさらに分割する
ステップ5	部分配列の要素数が 1 でこれ以上分割することができないので、2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ6	分割された部分配列をさらに分割する
ステップ7	2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ8	2 つの部分配列を統治する。統治するときに要素を昇順にソートする. ポイント：これら 2 つの部分配列の要素はすでにソート済みである
ステップ9-14	同様に、ステップ 2 で分割された部分配列を分割-統治する
ステップ15	2 つの部分配列を統治する。統治するときに要素を昇順にソートする. ポイント：これら 2 つの部分配列の要素はすでにソート済みである. 配列のソートが完了する

マージソートの流れの論理的な構造は、ツリー（木）となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。しかし、データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。

void main(){
    mergeSort( 配列全体 );
}

void mergeSort( 部分配列 ){
    if ( 部分配列の要素数が１以下 ) return;
    mergeSort( 部分配列の前半 );
    mergeSort( 部分配列の後半 );
    merge( 部分配列 );
}

void merge( 部分配列 ){
    すでにソートされている部分配列の前半と後半を昇順に統治（マージ）する.    
}

マージソートのプログラムは、mergeSort と merge の２つの部分から構成されています。まず、配列全体を指定した mergeSort を呼び出します。mergeSort は与えられた配列を前半後半の２つに分割します。その２つについてそれぞれさらに mergeSort を行います（再帰により実現する）。mergeSort は配列の要素数が 1 以下のときは何もせずに終了します。そして、各 mergeSort の最後で、分割された前後２つの配列を merge します。merge を実行する時点で、mergeSort( 部分配列の前半 ) と mergeSort( 部分配列の後半 ) がすでに終了しているので、merge はすでにソートされている部分配列の前半と後半に対して実行されます。言い換えれば、merge の役割は、すでにソートされている２つの部分配列を１つのソートされた部分配列にすることです。

プログラム例：部分配列の先頭のインデックスを left、部分配列の(末尾 + 1)のインデックスを right とした場合

void mergeSort( Data data[], int left, int right ){
    if ( left >= right - 1 ) return;
    int mid = ( left + right ) / 2;
    mergeSort( data, left, mid );
    mergeSort( data, mid, right );
    merge(data, left, mid, right );
}

void merge( Data data[], int left, int mid, int right ){
    Data L[MAX/2 + 2], R[MAX/2 + 2]; // temporal buffers
    int n1 = mid - left; // size of L
    int n2 = right - mid; // size of R
    for ( int i = 0; i < n1; i++ ) L[i] = data[left + i];
    for ( int i = 0; i < n2; i++ ) R[i] = data[mid + i];
    L[n1].key = R[n2].key = INT_MAX;
    int i, j;
    i = j = 0;
    for ( int k = left; k < right; k++ ){
        if ( L[i] <= R[j] ) { data[k] = L[i++]; }
        else data[k] = R[j++];
    }
}

この merge 関数は番兵を使ってやや巧妙な処理をしています。以下の図は、この merge のメカニズムをカードの操作で表したものです。左右にカードの束があり、各束のカードは小さい順に整列されているものとします。そして、カードの最下部に番兵としてジョーカーを追加配置します。

マージの処理は、各カードの山のてっぺんの値を比べ、小さい方を選択して順番に並べていきます。この操作の過程で、あるカードとジョーカーを比べる局面が発生しますが、ジョーカーが選ばれることはありません。つまり、番兵にはどのカード（数字）と比べても負けることのない大きな数を割り当てるのです。

ジョーカーすなわち番兵の設置によって、マージの際にカードの束が空になったか否かのチェックをする必要がなくなります。なぜなら、カードを選択する回数を、ジョーカーを除いたカードの合計値とすれば、ジョーカーが比べられることも、カードの束が空になることもないからです。束が空になったか否かのチェックは、プログラム上では配列の範囲を超えるか否かのチェックとなるので、番兵の設置は処理の高速化にも繋がり（微々たるものですが、）プログラムが読みやすくなります。




次に示す、merge のプログラムは、さらに巧妙なテクニックを用いています。プログラムの動作を考えてみましょう。

void merge( Data data[], int left, int mid, int right ){
    Data T[MAX]; // temporal buffer
    int i, j;
    for ( i = left; i < mid; i++ ) T[i] = data[i];
    for ( i = mid, j = right - 1; i < right; i++, j-- ) T[i] = data[j];
    i = left; j = right - 1;
    for ( int k = left; k < right; k++ ){
        if ( T[i] <= T[j] ) { data[k] = T[i++]; }
        else { data[k] = T[j--]; }
    }
}

マージソートの計算効率は、データがどのような特徴を持っていても O(nlogn) となります。上図に示したマージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるからです。

実戦でマージソートを自分で最初から実装することはまずないと思われますが、分割統治法、再起、番兵のアイデア、などを学べる良いアルゴリズムの１つではないでしょうか。

バブルソート Bubble Sort

選択ソートはある決められた範囲から、最小値を見つけ要素の交換を行いました。バブルソートは、隣り合う要素の比較のみを繰り返すことによって並び替えを行います。

バブルソートのアルゴリズムを以下に示します。

各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。 未ソートの部分がなくなるまで、以下の処理を繰り返します。 データの先頭から隣どうしを比較して、大小関係が逆ならばそれらを交換していきます。この交換処理を未ソートの部分の末尾まで順番に行います。

バブルソートはその名前からイメージできるように、泡（Bubble）が水面に上がっていくようにデータが動いていきます。上記のアルゴリズムでは、ソートされたデータが配列の後ろから順番に決定されていきます。

具体的な例で、バブルソートの流れを初期状態から見てみましょう。上図に示す処理が終了すると、データの中で一番大きい要素が配列の末尾に移動します。続きの処理を下図に示します。



上図のステップ1.～5.が終了すると、データの中で2番目に大きい要素が配列の後ろから2番目に移動します。以下同様に、ステップ6.～9.、ステップ10.～12.、ステップ13.～14.でそれぞれソート済みの部分に追加されるデータが決まっていきます。

以下のプログラムはは、データの数 size　を読み込み、size個の整数のデータを配列 data に読み込んで、配列の要素をバブルソートによって昇順に整列し、それを出力します。プログラムの本体である bubbleSort を見てみましょう。下図に示すように、07行目の最初のループ変数であるendは未ソートの部分の末尾を示します。08行目のforループによってデータの先頭からendまでの範囲で、隣どうしを比較して逆順ならば交換する処理を繰り返します。この２番目のループが終わると、その範囲のなかで一番大きい値がソートされていない部分の末尾に移動します。

#include<iostream>
using namespace std;

#define MAX 100

void bubbleSort( int size, int data[] ){
    for ( int end = size - 1; end > 0; end-- ){
        for ( int j = 0; j < end; j++ ){
            // 隣どうしを比較して、逆順ならば交換
            if ( data[j+1] < data[j] ){
                int tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

バブルソートの計算量を考えてみましょう。データの数をnとすると、バブルソートは未ソートの部分における隣どうしの比較演算をn-1回、n-2回、n-3回、・・・、1回行います。よって合計の比較演算の回数は(n²-n)/2となり、バブルソートはO(n²)のアルゴリズムとなります。

練習問題

選択ソート セレクションソート Selection Sort

選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの１つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

	各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
	1.「未ソートの部分」から最小の要素を探します。
	2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
	1. 2. を未ソートの部分がなくなるまで繰り返します。

1. 初期状態は全ての要素が未ソートの部分に属します。 2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。 3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。 4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。 5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。 6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。 7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。 8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。 9. ソートが完了します。

#include<iostream>
using namespace std;

#define MAX 100

void selectionSort( int size, int data[]){
    for ( int front = 0; front < size - 1; front++ ){
        // 最小値のインデックスを探す
        int minIndex = front; 
        for ( int j = front + 1; j < size; j++ ){
            if ( data[j] < data[minIndex] ) minIndex = j;
        }
        // 未ソート部分の先頭と最小値を交換
        int tmp = data[front];
        data[front] = data[minIndex];
        data[minIndex] = tmp;
    }
}

Program は、データの数 size　を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。

選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n²-n)/2となり、選択ソートはO(n²)のアルゴリズムとなります。

ソートのアルゴリズム

様々なソートアルゴリズムが考案されてきましたが、用途やデータの特徴、またはプログラムで使うデータ構造などに応じて、それらを的確に選ばなくてはなりません。以下の表は、代表的なソートのアルゴリズムとそれらの効率・特徴を示しています。

アルゴリズムの名前	効率	安定性	特徴
選択ソート (Selection Sort)	O(n2)	×	単純で最も直感的だが、効率が悪い
バブルソート (Bubble Sort)	O(n2)	○	単純だが効率が悪い
挿入ソート (Insertion Sort)	O(n2)	○	ぼぼ整列されているデータに対して効率的
マージソート (Merge Sort)	O(nlonn)	○	外部の記憶領域が必要
ヒープソート (Heap Sort)	O(nlonn)	×	ヒープのデータ構造を応用する
クイックソート (Quick Sort)	O(nlonn)	×	ほぼ整列されているデータに対して効率的ではない

選択ソート、バブルソートはソートのアルゴリズムの導入に紹介されるくらいで、実践で（現場で）使うことはほんとんどありません。データの特徴や問題の仕様に合わせて適切なアルゴリズムを設計することが重要です。マージソートは安定で高速、しかも実装が比較的容易なのでおすすめです。クイックソートは、理論上最速と言われていますが、安定ではないので注意が必要です。

安定なソート

アルゴリズムを設計、選ぶ際に重要なポイントとなるのがその効率ですが、整列のアルゴリズムに関しては、それが「安定なソート」であるかを考慮に入れなくてはなりません。安定なソートとは、キーの値が同じ要素が２つ以上あるデータセットにおいては、それらの要素をソート前とソート後で順番が変わらないようなソート方法です。以下の例を見てみましょう。





上の例は、同じデータを整列したもので、どちらの配列もデータが昇順に並べ替えられましたが、左が「安定なソート」、右が「安定でないソート」です。このデータには、２つの「３」があります。「緑の３」と「青の３」です。初期データは、「緑の３」→「青の３」の順番となっていますが、「安定なソート」ではこの順番が保たれています。一方、「安定でないソート」では、「青の３」→「緑の３」と順番が逆になっています。

このソートの安定性を考慮に入れなければ、思わぬ失敗をしてしまいます。

整列 ソート

整列されたデータは探索（検索）し易い、ということをすでに紹介しました。データの整列は、多くのアルゴリズムの基礎になります。たくさんのデータを、あるキーに従って昇順（小さい順）または降順（大きい順）に整列するためのアルゴリズムをいくつか記録したいと思います。

• 安定なソート
• ソートのアルゴリズム
• バブルソート
• 選択ソート
• マージソート