#pragma twice

KAB-studio > プログラミング > #pragma twice > 255 Version 13.19 マージソートのコーディング

#pragma twice 255 Version 13.19 マージソートのコーディング

前のページへ 表紙・目次へ 次のページへ

 Version 13.19
マージソートのコーディング

前回は、マージソートの仕組みについて説明しました
ってことは今回はコードね
というわけで、マージソートの関数です

void DoMergeSort( int *p_piAry, int p_iSize )
{
    // A
    if( p_iSize <= 1 )
    {
        // 要素数が1以下なら何もしません。
        return;
    }

    // B
    // 中央から左側のサイズを取得します。
    int iLeftSize = p_iSize / 2;
    // 中央から右側のサイズを取得します。
    int iRightSize = p_iSize - iLeftSize;
    // 中央から左側のサイズの配列を作成します。
    int *piLeftAry = new int[iLeftSize];
    // 中央から右側のサイズの配列を作成します。
    int *piRightAry = new int[iRightSize];
    // それぞれコピーします。
    int iF1;
    for( iF1 = 0; iF1 < iLeftSize; ++iF1 )
    {
        piLeftAry[iF1] = p_piAry[iF1];
    }
    
    for( iF1 = 0; iF1 < iRightSize; ++iF1 )
    {
        piRightAry[iF1] = p_piAry[iLeftSize + iF1];
    }

    // C
    // それぞれ再帰呼び出しします。
    DoMergeSort( piLeftAry, iLeftSize );
    DoMergeSort( piRightAry, iRightSize );

    // D
    // マージします。
    int iLeftPos = 0;
    int iRightPos = 0;
    while(
        ( iLeftPos  < iLeftSize  ) || 
        ( iRightPos < iRightSize )
        )
    {
        // 左右両方とも配列の中にいる間、ループします。

        if( iRightSize <= iRightPos )
        {
            // 右側が配列の最後まで来ている場合。
            // 左側を追加します。
            p_piAry[iLeftPos + iRightPos] = piLeftAry[iLeftPos];
            ++iLeftPos;
        }
        else if( iLeftSize <= iLeftPos )
        {
            // 左側が配列の最後まで来ている場合。
            // 右側を追加します。
            p_piAry[iLeftPos + iRightPos] = piRightAry[iRightPos];
            ++iRightPos;
        }
        else if( piLeftAry[iLeftPos] > piRightAry[iRightPos] )
        {
            // 左側の方が右側より大きい場合。
            // 右側を追加します。
            p_piAry[iLeftPos + iRightPos] = piRightAry[iRightPos];
            ++iRightPos;
        }
        else
        {
            // それ以外の場合(左側の方が右側より小さい場合)。
            // 左側を追加します。
            p_piAry[iLeftPos + iRightPos] = piLeftAry[iLeftPos];
            ++iLeftPos;
        }
    }

    // E
    // 解放します。
    delete[] piLeftAry;
    delete[] piRightAry;
}

長!
使用例はこちら

void Use_DoMergeSort()
{
    int iAry[5];
    iAry[0] = 4;
    iAry[1] = 9;
    iAry[2] = 3;
    iAry[3] = 5;
    iAry[4] = 8;

    // ソートします。
    DoMergeSort( iAry, 5 );

    for( int iF1 = 0; iF1 < 5; ++iF1 )
    {
        TRACE( "%d ", iAry[iF1] );
    }
    TRACE( "\n" );
    // 3 4 5 8 9 
}

使い方は普通ね
それでは、少しずつ見ていきます。まずA〜B
サイズが 1 以下だったら return ……いきなり関数終了しているね
これはあとで説明します
いきなりかい!
というわけで次、B〜C
長さ取って長さ取って、 new して new して、 for して for して
ここは〈分割〉フェーズ。前回の例で説明するね

4 9 3 5 8 

このデータを、前回はいっぺんにバラバラにしたけど、実際のプログラム
ではふたつずつに分けて、 new で作った配列にコピーしていきます
サイズを 2 で割って左右のサイズを出すわけね。なんかクイックソート
に似てる……
分割してコピー、をイメージするとこんな感じかな

(4,9) (3, 5, 8)
 4  9  3  5  8 

 () で囲んだところが new で作った動的配列
左右 new で作って、そこに for でループして1個ずつコピーするわけ

このコピーが終わったら、次は再帰呼び出し
 Version 13.16 ( No.252 ) のアレね。自分の関数をもう一度呼ぶって
ゆー。あ、ってことは

    // それぞれ再帰呼び出しします。
    DoMergeSort( piLeftAry, iLeftSize );
    DoMergeSort( piRightAry, iRightSize );

のとこがそうね
そう、このC〜Dの箇所でもう一度自分自身を呼びます。この呼び出しは
さっき分割したそれぞれに対して。つまり

(4,9) 
(3, 5, 8)

このふたつ別々に呼び出します
呼び出すと?
また分割。たとえば上のだと

(4) (9)<分割後
(4 , 9)<分割前

というふうに分けられます。さらにこれが
再帰呼び出しで呼ばれる
すると、たとえば (4) は、サイズが 1 だから
あ、A〜Bの if で引っかかるね
そういうこと。 (9) も同様。なので、 (4) (9) の場合、C〜Dの再帰呼
び出しをすると、何もせずにすぐに返ってきます
そこでD〜Eね
この while のループはマージ箇所。

(4) (9)<分割後
(4 , 9)<分割前

この〈分割後〉の方を小さい順に〈分割前〉へとコピーしていきます。 
まず、while は、分割したふたつの配列を全部チェックする、っていう
ループ
ふたつチェックしてるね
で、そのループの中で4つの if でチェックしてます。最初のふたつの 
if は〈片方がマージし終えてたら、もう片方のを無条件に入れる〉ってい
う簡単な話

前回の例で言うと

(9)
()
 ↓
[3,4,5,8,]

この状態のこと。下の () にはもうマージする数が存在しないから
何も考えずにもう片方の (9) からマージしちゃえ、ってことね
そういうこと。残りのふたつは単純な比較

(9)
(8)
 ↓
[3,4,5,,]

という状態の時に、小さい方をマージする、っていうこと
4つ if があるけど、上2つと下ふたつに分かれてる感じね
このマージを繰り返していけば、ふたつの分割した配列が元の配列にマー
ジされます
あ、そか、引数で渡されてる配列にマージしてるんだね
そう。だから、最終的には
ソート元の配列にマージされるわけね
そういうこと。最後に、分割したときに作った配列を解放して、1段階完

これを繰り返して完全にマージ完了、ね

/*
    Preview Next Story!
*/
って説明されるとわかるんだけどねー
実際に作れない?
作れない作れない
というわけで、使うだけのバージョンを用意しました
おー
というわけで次回
< Version 13.20 マージソート・汎用版 >
につづく!
でもいつかは作れるようにね
無理です
 
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
RSSに登録
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
 
このページは、Visual C++ 6.0を用いた C++ 言語プログラミングの解説を行う#pragma twiceの一コンテンツです。
詳しい説明は#pragma twiceのトップページをご覧ください。