マージソート 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 回の比較演算がなされるからです。

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

ナップザック問題 Knapsack Problem

大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます)

この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2^N) となります。N が数十個でも、実用的な時間では計算できません。

品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。

C[i][w] が、大きさ w のナップザックに品物を 0 から i 個目まで考慮した時の価値の合計の最大値、となるような (N+1) × (W+1) の２次元配列 C を準備します。

C[i][w] の値は、

(1) C[i - 1][w - 品物 i の重さ] + 品物 i の価値、　または
(2) C[i - 1][w]

の大きい方となります。ここで、(1)はこの時点で品物 i を選択する、（２）はこの時点で品物 i を選択しない、という処理に対応します。ただし、（１）の場合は、品物 i の重さが w を超えない場合に限ります。

例を見てみましょう。

ナップザックの大きさ w が 0、または品物の数 i が 0 個の場合は、価値の合計が 0 なので、w = 0 と i = 0 の部分を 0 に初期化します。 大きさ w が 1 のナップザックに、品物 1 を入れてみる。 しかし、品物 1 の大きさは 2 で、容量を超えるので、無条件で品物 1 は選択しない（できない）。 大きさ w が 2 のナップザックに、品物 1 を入れてみる。 ここで、品物 1 の大きさは 2 なので選択可能。 (1) 選択した場合は 0 + 4 = 4 （斜めの矢印）、 (2) 選択しない場合は 0　（縦の矢印）, なので、C[i][w] = C[1][2] に 4 を記録する。 大きさ w が 3, 4, 5 についても同様。 大きさ w が 1 のナップザックに、品物 2 を入れてみる。 しかし、品物 2 の大きさは 2 で、容量を超えるので、無条件で選択しない。 大きさ w が 2 ～ 5 のナップザックに、品物 2 を入れてみる。 C[2][4] に注目してみましょう。ここでは (1) C[1][2] + 品物 2 の価値　（= 4 + 5）または (2) C[1][4]　（= 4）` のいづれか大きいほうを選びます。 大きさ w が 1 ～ 5 のナップザックに、品物 3 を入れてみる。 同様に C[i][w] を計算する。 品物 3 の重さが 1 なので、斜めの矢印の幅が 1 になる。 大きさ w が 1, 2 のナップザックに、品物 4 を入れてみる。 しかし、品物 4 の大きさは 3 で、容量を超えるので、選択できない。 容量を超えるとは、斜めの矢印が配列からはみ出してしまうことに相当する。。 大きさ w が 3, 4, 5 のナップザックに、品物 4 を入れてみる。 今度は、大きさが 3 なので、矢印の幅は 3 。 C[N][W] が価値の最大値。 ここから、矢印を伝っていくと、選ぶべき品物を記録することができる。 すなわち、斜めの矢印が品物の選択を表している。

#include<iostream>
#include<vector>
#define MAX 100
#define DIAGONAL 1
#define LEFT 0

using namespace std;
/**
* Target 624, 10130,
*
*/

struct Item{
    int value, weight;
};

int n;
Item items[MAX];
int C[MAX+1][MAX+1], G[MAX+1][MAX+1];
int weight;

void compute( int &maxValue, vector<int> &path ){
    for ( int w = 0; w <= weight; w++ ) {
        C[0][w] = 0;
        G[0][w] = DIAGONAL;
    }
    
    for ( int i = 1; i <= n; i++ ) C[i][0] = 0;
    
    for ( int i = 1; i <= n; i++ ){
        for ( int w = 1; w <= weight; w++ ){
            if ( items[i].weight <= w ){
                if ( items[i].value + C[i-1][w - items[i].weight] > C[i-1][w] ){
                    C[i][w] = items[i].value + C[i-1][w - items[i].weight];
                    G[i][w] = DIAGONAL;
                }else{
                    C[i][w] = C[i-1][w];
                    G[i][w] = LEFT;
                }
            }else {
                C[i][w] = C[i-1][w];
                G[i][w] = LEFT;
            }
        }
    }
    
    maxValue = C[n][weight];
    
    path.clear();
    int w = weight;
    
    for ( int i = n; i >=1; i-- ){
        if ( G[i][w] == DIAGONAL ){
            path.push_back( i );
            w -= items[i].weight;
        }
    }
    
    reverse( path.begin(), path.end() );
}

void input(){
    cin >> n >> weight;
    for ( int i = 1; i <= n; i++ ){
        cin >> items[i].value >> items[i].weight;
    }
}

main(){
    int maxValue;
    vector<int> path;
    input();
    compute( maxValue, path);
    
    cout << "max " << maxValue << endl;
    for ( int i = 0; i < path.size(); i++ ) cout << path[i] << endl;
    
    for ( int i = 1; i <= n; i++ ){
        for ( int j = 1; j <= weight; j++ ) {
            printf("%5d", C[i][j]);
        }
        cout << endl;
    }
    
}