《052》マージソート(2)

 
マージソートのアルゴリズムを利用したプログラム例

 int型整数のソートに、マージソートのアルゴリズムを利用したプログラムです。
#include <random>
#include <iostream>

void mergesort(int* base, int nmemb)
{
    // 要素数 1以下なら何もしない。
    if (nmemb <= 1) return;

    // 配列用の領域を確保
    int* temp = new int[nmemb];

    // 分割位置の添字 m を決定
    int m = nmemb / 2;

    // 分割左側から mergesort を再帰呼出し
    mergesort(base, m);

    // 分割右側から mergesort を再帰呼出し
    mergesort(&base[m], nmemb - m);

    for (int i = 0; i < nmemb; i++) {
        // ソート済の左側と、
        //         同じくソート済の右側を、
        //         配列 temp にコピー
        temp[i] = base[i];
    }

    int p = 0;  // 分割左側の最初の添字
    int q = m;  // 分割右側の最初の添字

// 配列 temp の左側と右側は、それぞれソー
//         ト済みなので、左右の要素を比較
//         しながら、
//         昇順になるように配列 base にコ
//         ピーしていきます。
// 以下は、その作業です。
    int i = 0;
    do {
        if (temp[p] < temp[q]) {
            base[i] = temp[p];
            p++;
        }
        else {
            base[i] = temp[q];
            q++;
        }
        i++;
    } while (p < m && q < nmemb);

    if (p == m) {
        for (; i < nmemb; i++) {
            base[i] = temp[q];
            q++;
        }
    }
    else if (q == nmemb) {
        for (; i < nmemb; i++) {
            base[i] = temp[p];
            p++;
        }
    }

    // この for文はソートの途中経過を出力
    //         するためのものなので、削除
    //         しても問題ありません。
    for (int i = 0; i < nmemb; i++)
        std::cout << temp[i] << " ";
    std::cout << '\n';

    // 領域を解放します。
    delete[] temp;
}


int main() {
    std::random_device rd;

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

    for (int i = 0; i < nmemb; i++) {
        a[i] = rd() % 90 + 10;
    }

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

    mergesort(a, nmemb);

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


e03_0032.png

2018-03-12 00:29 : 未分類 : コメント : 0 :
コメントの投稿
非公開コメント

« next  ホーム  prev »

検索フォーム

こうすけ kousuke_cpp@outlook.jp

スポンサーリンク

新版 明解C 中級編 (明解シリーズ)

新品価格
¥2,916から
(2018/3/24 23:58時点)