《その161》マージソート（１）: C++，C++/CX に挑戦！

2017年12月03日

《その161》マージソート（１）

　マージソート（１）

　下のマージソートのプログラムは、はっきり言って良くないです (//△//)。
「先ず配列を分割する」の意味と、「再帰的な処理」の扱い方があいまいなまま作業に入ったのが良くなかったです。
　無駄の多いプログラムを書いているうちに、それらのことが少し理解できたので、次回にもう少しマシなプログラムを作りたいと思っています。

　だだ、無駄は多いのですが、ソートしていく手順としてはマージソートになっているので、一応下記しておきます。

　最後に掲載してある実行結果の画面コピーで、数字の並びがマージソートされる過程を確認できるのではないかと思います。


// ------------------------------------
#include <iostream>

int main() {
    int a[]
        = { 25, 21, 16, 12, 17, 11, 23, 19, 28, 17, 13,
            22, 24, 11, 18, 26, 19, 10, 21, 17, 19, 16, 14};

    int nmemb = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < nmemb; i++)
        std::cout << a[i] << " ";
    std::cout << '\n';

    int nmem = nmemb;
    int p = 0;
    while (nmem /= 2) p++;

    if (nmemb > (int)pow(2, p))
        nmem = (int)pow(2, p + 1);

    int* f = new int[nmem];
    int* g = new int[nmem];

    for (int i = nmemb; i < nmem; i++)
        f[i] = INT_MAX;

    for (int i = 0; i < nmemb; i++)
        f[i] = a[i];

    for (int i = 0; ; i++) {
        for (int j = 0; j < nmem / pow(2, i + 1); j++) {
            // pow(2, i + 1) … 2 の i + 1 乗
            //                  操作対象範囲の要素数
            //                  pow(2, i + 1) = 2, 4, 8, ･･･
            int nl = (int)pow(2, i);
            // pow(2, i) は操作対象範囲の左側要素数
            //                  pow(2, i) = 1, 2, 4 ･･･
            if (nl >= nmem) goto END;
            // 操作対象範囲の左側要素数が、配列 f の要素数以上に
            //                                    なったら作業終了。
            int nr = nl;
            // 操作対象範囲の右側要素数

            int xleft = (int)pow(2, i + 1) * j;
            // 操作対象範囲左側の左端要素の添字
            int xrght = xleft + nl;
            // 操作対象範囲右側の左端要素の添字
            int xl = xleft;
            int xr = xrght;

            for (int k = 0; k < nl + nr; k++) {
                // 操作対象範囲内の要素の個数と同じ回数だけの繰返し
                if (
                    f[xl] <= f[xr] && xl < xleft + nl
                    || xr >= xrght + nr
                )
                // ｢ f[xl] <= f[xr] 
                //      かつ xl が操作対象範囲左側に収まっている ｣
                //      または ｢ xr が操作対象範囲右側を超えている ｣
                    g[xleft + k] = f[xl++];
                    // f[xl] の値を臨時の配列 g に収容し、xl++ する。
                else if (xr < xrght + nr) {
                // そうではない場合
                    g[xleft + k] = f[xr++];
                    // a[xr] の値を臨時の配列 g に収容し、xr++ する。
                }
            }            
        } // j{ }

        for (int i = 0; i < nmemb; i++) {
            a[i] = f[i] = g[i];
        }
 
        for (int i = 0; i < nmemb; i++)
            std::cout << a[i] << " ";
        std::cout << '\n';

    } // i{ }

    delete[] f;
    delete[] g;

END:
   ;
}
// ------------------------------------