Version 13.16
クイックソートのコーディング
「前回はクイックソートのアルゴリズムについて説明しました」
『今回はコーディング？』
「そう。クイックソートを実際にプログラムにしてみます。ちょっと複雑だ
から注意してね」
void QuickSortImpl( int *p_piAry, int p_iFirst, int p_iLast )
{
// セパレータとなる値を取得。
int iSeparator
= p_piAry[p_iFirst + ( ( p_iLast - p_iFirst ) / 2 )];
// インデックス取得。
int iLeft = p_iFirst;
int iRight = p_iLast;
// 無限ループ。
while( 1 )
{
// 左から見て、セパレータ以上の値まで移動。
while( p_piAry[iLeft] < iSeparator )
{
++iLeft;
}
// 右から見て、セパレータ以下の値まで移動。
while( iSeparator < p_piAry[iRight] )
{
--iRight;
}
if( iRight <= iLeft )
{
// 交差していたので抜けます。
break;
}
// 入れ替え。
int iTemp = p_piAry[iLeft];
p_piAry[iLeft] = p_piAry[iRight];
p_piAry[iRight] = iTemp;
// 入れ替え箇所を飛ばすため、ひとつ進めます。
++iLeft;
--iRight;
}
if( p_iFirst < iLeft - 1 )
{
// 左側の要素数が 1 よりも多ければ、
// 左側を再ソートします。
QuickSortImpl( p_piAry, p_iFirst, iLeft - 1 );
}
if( iRight + 1 < p_iLast )
{
// 右側の要素数が 1 よりも多ければ、
// 右側を再ソートします。
QuickSortImpl( p_piAry, iRight + 1, p_iLast );
}
}
// 呼び出し元。
void DoQuickSort( int *p_piAry, int p_iSize )
{
// 配列の先頭と最後を渡します。
QuickSortImpl( p_piAry, 0, p_iSize - 1 );
}
『呼び出し元？』
「 DoQuickSort() は外から呼び出すための関数。そこから呼んでる
QuickSortImpl() は、実際にクイックソートをする関数」
『？ なんでふたつに分けてるの？』
「それは QuickSortImpl() の説明をしてからの方がいいかな。前回説明し
たように、クイックソートは、大きい方と小さい方に分けて、分割して、
っていうのを繰り返します」
『並び替えて分けての繰り返しね』
「そこで、この１セットの処理だけを QuickSortImpl() するようにしま
す」
『？』
「つまり、 QuickSortImpl() を呼んで左右に分けたあと、ふたつに分割し
たそれぞれの処理を、また QuickSortImpl() を呼んでその中で処理するよ
うにしています」
『あ、そういえば QuickSortImpl() の中で QuickSortImpl() を呼んで
る……こんなことできるんだ』
「そう。関数の中から自分と同じ関数を呼べるんです。この、自分自身を呼
ぶことを【再起呼び出し】って言います」
『さいきよびだし、ね』
「単語は有名だから憶えておいてね。今回の例では、再帰呼び出しをするこ
とでプログラムを簡略化しています」
『再帰呼び出しを使わないとどうなるの？』
「２重ループで回すことになるかな。ちょっと大変かも……」
『……ん？ で、 DoQuickSort() はなんであんの？』
「ああ、 QuickSortImpl() は分割する度に呼ぶでしょ。そのとき、引数に
は〈配列〉と〈分割した範囲の左端〉と〈分割した範囲の右端〉を渡しま
す」
『それでどの範囲をソートするかってするわけね』
「そういうこと。でも、一番最初に呼ぶときは、こういうふうに範囲で渡す
のは面倒。今まで通り〈配列〉と〈サイズ〉の方がわかりやすいから」
『だから DoQuickSort() はその配列とサイズでその中で……』
QuickSortImpl( p_piAry, 0, p_iSize - 1 );
『最初の分割は、全体だから、一番左端の 0 と、一番右端の、サイズ - 1
を渡してるわけね』
「そういうこと。 QuickSortImpl() を直接呼んでも問題ないんだけど、こ
の方がわかりやすいからね」
『これまでもそうだったしね』
「さて、この使用例」
void Use_DoQuickSort()
{
int iAry[5];
iAry[0] = 4;
iAry[1] = 9;
iAry[2] = 3;
iAry[3] = 5;
iAry[4] = 8;
// ソートします。
DoQuickSort( iAry, 5 );
for( int iF1 = 0; iF1 < 5; ++iF1 )
{
TRACE( "%d ", iAry[iF1] );
}
TRACE( "\n" );
// 3 4 5 8 9
}
『この辺はいつも通りね』
「では、 QuickSortImpl() の中身について見てみます。まず〈大きい数〉
と〈小さい数〉の境界になる数字を取得します」
// セパレータとなる値を取得。
int iSeparator
= p_piAry[p_iFirst + ( ( p_iLast - p_iFirst ) / 2 )];
『これは位置的に真ん中ってわけね』
「前回言ったように、全部出して個数で割って、平均値を出すのもありだか
ら」
『でもちょっと重そう……』
「クイックソートはこの数によって早さが違ってくるからね、そのくらいす
るのもありかも。では次、ループ開始」
// 無限ループ。
while( 1 )
『無限ループね』
「左右両方から見ていくっていう処理だから、 for よりはこういう方がわ
かりやすいかな」
『次は左から見ていくところね』
// 左から見て、セパレータ以上の値まで移動。
while( p_piAry[iLeft] < iSeparator )
{
++iLeft;
}
『ん？ 比較用の関数って使わないの？』
「使ってもいいけど、ちょっとここの記述が複雑になるかな。次の関係もあ
るし」
// 右から見て、セパレータ以下の値まで移動。
while( iSeparator < p_piAry[iRight] )
{
--iRight;
}
『右から見ていくのね。あれ？ そか、 == がないから、さっきの逆ってわ
けじゃないんだ』
「このあたりはアルゴリズムの重要な箇所だから、ちゃんと調べてから変え
た方がいいかも」
『ちょっと難しそう……』
「次は、右と左が交差したかのチェック」
『これで無限ループから抜けるのね』
「次は左右の入れ替え」
『これはおなじみね』
「ループの最後では、今入れ替えた箇所をもう一度見ないように、ひとつ進
めます」
// 入れ替え箇所を飛ばすため、ひとつ進めます。
++iLeft;
--iRight;
『見てもしょうがないものね』
「さて、ループが終わったら、左右に分割してそれぞれまた呼び出します。
まず左側」
if( p_iFirst < iLeft - 1 )
{
// 左側の要素数が 1 よりも多ければ、
// 左側を再ソートします。
QuickSortImpl( p_piAry, p_iFirst, iLeft - 1 );
}
「この if は、左と右が見終わった段階で、その境界の左側が２個以上だっ
たら、それを再ソートします」
『これが再帰呼び出しのとこね。１個の時にソートしないのは……意味ない
もんね』
「そういうこと。右側も同じ」
if( iRight + 1 < p_iLast )
{
// 右側の要素数が 1 よりも多ければ、
// 右側を再ソートします。
QuickSortImpl( p_piAry, iRight + 1, p_iLast );
}
「こうやって分割していって、もうこれ以上分割できなくなったら終了で
す」
/*
Preview Next Story!
*/
『や、ややこしい……』
「再帰呼び出しすると複雑になるからね」
『これ、１から作れって言われても無理かも……』
「作る必要はないんだけどね」
『え？』
「というわけで次回」
＜ Version 13.17 ランタイムでクイックソート ＞
『につづく！』
「実はランタイムにあるんです」
『えええ！？？ 無駄骨ですか！？』
users
users
