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 一番便利・マージソート ＞
「につづく！」
『ランタイムないといやー！』
「でも、僕が関数の例を作ってあげてるんだけど……」
『あ、そっか』
users
users
