Version 13.17
ランタイムでクイックソート

「前回は、クイックソートする関数を作ってみました」
『再帰呼び出ししててちょっと複雑だったかも……』
「さて、実はあの関数は必要ありません」
『ええっ？』
「クイックソートは、専用の関数がランタイムに用意されてるからです」
『え”、なに無意味？』
「アルゴリズムの勉強だから無意味じゃないんだけど……」
『でもなんか無駄～』
「でも、仕組みがわからなきゃ安定ソートじゃないとかの理由がわからない
でしょ」
『う”』
「だから、実際に作ってみることが必要ってこと」
『うー』
「さて、ではこれからランタイムのクイックソート用関数 qsort() を使っ
てみます」
『 qsort() 、そのままね』
「ちなみにクイックソート以外のソート関数は用意されてません」
『げ、じゃあ安定ソートできないじゃん』
「なんだよね。だからこれもあまり使う機会ないかも。まぁそれは置いとい
て、まずは使ってみましょう」

// 比較用関数。 int で比較します。
// 左の方が小さければマイナス、
// 同じであれば 0 、
// 左の方が大きければプラスを返します。
int CompareTo( const void *p_pvL, const void *p_pvR )
{
    return *( (int *)p_pvL ) - *( (int *)p_pvR );
}

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

    // ソートします。
    qsort( iAry, 5, sizeof( int ), CompareTo );

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

『うわ、みじか！　ん、でも比較用関数は必要なんだ』
「そう、 Version 13.09 ( No.245 ) のときみたいに。でも微妙に違うで
しょ」
『……引数が void ポインタで、戻り値が int ……』
「 qsort() を使う上で、色々なルールがあるから、まずそのあたりをひと
つずつ押さえていきます。まずは呼び出している箇所から」

    // ソートします。
    qsort( iAry, 5, sizeof( int ), CompareTo );

「第１引数は配列、第２引数はその配列の要素数、第３引数はその要素のサ
イズ、第４引数は比較用関数へのポインタ」
『要素数とサイズ、両方渡すんだ』
「これは qsort() の引数を見た方が早いかな」

void qsort
    ( void *base
    , size_t num
    , size_t width
    , int (__cdecl *compare)(const void *elem1, const void *elem2) 
    );

「第１引数が void ポインタだから、各要素のサイズがわからないと〈次の
要素〉が見られないから」
『そか、今までのソートって普通の型の配列だったから、要素のサイズって
わかってたけど、 qsort() は void のポインタだから……って、なんで 
void ポインタなの？』
「そうじゃなきゃいろんな型が使えないでしょ」
『あ、 CObArray と同じね』
「そういうこと。 void ポインタは〈汎用型〉として使えるから便利なんだ
よね。その分、危険なんだけど」
『だよねー、型間違えたらエラーだし、コンパイルしたときにはわからない
し……』
「さて次に、比較用関数について」
『なんかややこしい引数だね』

    , int (__cdecl *compare)(const void *elem1, const void *elem2) 

「この引数は、【関数ポインタ】を引数として受け取るときの書き方」
『かんすうぽいんた？　そういえばアルゴリズムの最初の時に言ってたね』
「そう、この方法を使うと関数をとっかえひっかえできるから、アルゴリズ
ムには便利なんです」
『確かに、引数として渡せると便利ね……』
「じゃあ、この関数ポインタの見方について」

    戻り値 (呼出方 *変数)(引数) 

「という書式になっています」
『？』
「そうだね、普通に変数として使ってみようか」

void FunctionPointer()
{
    // 関数ポインタ。
    int (__cdecl *fp)(const void *elem1, const void *elem2);
    fp = CompareTo;

    int i50 = 50;
    int i100 = 100;
    // 関数ポインタ経由で呼び出し。
    TRACE( "%d\n", fp( &i50, &i100 ) );
    TRACE( "%d\n", fp( &i100, &i100 ) );
    TRACE( "%d\n", fp( &i100, &i50 ) );
    // -50
    // 0
    // 50
}

『んと、つまり fp って変数を作ってるってこと？』
「そういうこと。 CompareTo() の関数のアドレスを入れる変数 fp を作っ
て、その中に関数のアドレスを入れると、 fp が CompareTo() の代わりに
なるんです」
『ほほう、これを使えば、どの関数を呼ぶか、っていうのを引数で変えられ
るわけね』
「そういうこと。関数ポインタを直に扱うのは危険だからあまり使いすぎな
い方がいいけど、こういう方法もあるってこと」
『確かに便利は便利ね』
「ちなみに、火美ちゃんはこれまでになんども関数ポインタを使ったことが
あるんです」
『え”？　全然憶えないんだけど』
「ウィンドウプロシージャやダイアログプロシージャ」
『あ……あ！　そっか、あれって関数ポインタを渡してたんだ！』
「 Version 8.07 ( No.149 ) の」

    int iRet
        = DialogBox
            ( p_hInstance
            , MAKEINTRESOURCE( IDD_MAIN )
            , NULL
            , DialogProc
            );

「は、 DialogProc っていう関数ポインタを引数として渡していたんです」
『そうするとメッセージが来たら DialogProc() 呼んで渡す、ってできるも
んね。なるほどねー』
「 qsort() もこのウィンドウプロシージャも、関数の中から呼ぶ関数のポ
インタを渡すしてるでしょ」
『ややこしい……』
「関数ポインタの主な使い道がこれかな」
『他に使い道あるの？』
「配列に入れて立て続けに呼び出すとか」
『う”、なんか危険な香りが……』
「まぁね、実は C++ では【ポリモーフィズム】っていうのがあって、同じ
ような機能をもっと安全に使う方法があるから、最近はあまり使わないか
な」
『ポリモーフィズム、よく聞くけど……』
「ま、説明は今度ね。さて、話を戻して、今度は比較用関数そのものを見て
みます」

// 比較用関数。 int で比較します。
// 左の方が小さければマイナス、
// 同じであれば 0 、
// 左の方が大きければプラスを返します。
int CompareTo( const void *p_pvL, const void *p_pvR )
{
    return *( (int *)p_pvL ) - *( (int *)p_pvR );
}

『今までと戻り値と引数の型が違う！』
「引数の void ポインタは説明したでしょ」
『 Version 13.13 ( No.249 ) の？』
「そう、それと同じ。 void ポインタで受ければどんな型にでも使えるか
ら」
『ん？　それって qsort() の第１引数と同じ理由？』
「同じ理由。 qsort() っていうひとつ関数でどんな型でも扱えるようにす
るには、 void ポインタが一番簡単だからね」
『でも危険、と』
「そういうこと」
『戻り値が int なのはなんで？』
「比較方法がそうだから。〈より大きい〉と〈より小さい〉が必要だから」
『だから３つに分けてるわけね。でも…… if 使ってないね』

    return *( (int *)p_pvL ) - *( (int *)p_pvR );

『こんなんでいいの？』
「〈プラス〉と〈マイナス〉って、正確な数は決めてないから」
『あ、そういうえば…… 1 も 100 も同じ？』
「そういうこと。だから単純に引き算すればいいだけ」
『そうすれば、左が大きければプラス、小さければマイナス、同じなら 0 
ってなるわけね、なるほど』
「ちょっとわかりにくいから、丁寧に書いてもいいかもね。ではまとめ。
qsort() はこんなに簡単に使えます」
『ホント、簡単ね……』
「なので、クイックソートをする場合には qsort() を使いましょう」
『はーい』
「さらに言えば、安定ソートをしない場合には qsort() を使いましょう」
『最速だもんね』
「そういうこと。あるものをできる限り使うのが一番だからね」

/*
    Preview Next Story!
*/
『やっぱランタイムがあると簡単ねー』
「さて、次回はマージソートの説明をします」
『ランタイムある？』
「ありません」
『というわけで次回』
＜ Version 13.18 一番便利・マージソート ＞
「につづく！」
『ランタイムないといやー！』
「でも、僕が関数の例を作ってあげてるんだけど……」
『あ、そっか』