Version 13.09
ソートの中身のバリエーション
「というわけで前回の続き」
『こんな関数だったよね』
void DoBubbleSort( int *p_piAry, int p_iSize )
{
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// 最後から先頭方向へのループです。
// ただし「入れ替え先」までです。
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
{
if( p_piAry[iIn - 1] > p_piAry[iIn] )
{
// 前の方が大きいので入れ替えます。
int iTemp = p_piAry[iIn];
p_piAry[iIn] = p_piAry[iIn - 1];
p_piAry[iIn - 1] = iTemp;
}
}
}
}
「使用例はこう」
void Use_DoBubbleSort()
{
int iAry[5];
iAry[0] = 4;
iAry[1] = 9;
iAry[2] = 3;
iAry[3] = 5;
iAry[4] = 8;
// ソートします。
DoBubbleSort( iAry, 5 );
for( int iF1 = 0; iF1 < 5; ++iF1 )
{
TRACE( "%d ", iAry[iF1] );
}
TRACE( "\n" );
// 3 4 5 8 9
}
『おー、ソートできてる』
「基本的には前回説明したとおり。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
「が入れ替え先のループ」
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
「が各周のループ」
if( p_piAry[iIn - 1] > p_piAry[iIn] )
「が比較部分」
int iTemp = p_piAry[iIn];
p_piAry[iIn] = p_piAry[iIn - 1];
p_piAry[iIn - 1] = iTemp;
「が入れ替え部分」
『入れ替えるとこは前回省略したとこだね。でもフツー』
「だから省略したんだし……さて。ここで、バリエーションについて見てみ
ます」
『バリエーションって、いろんなソートってやつ？』
「そうじゃなくて、バブルソートはバブルソートなんだけど、それ以外の部
分を変えてみよう、っていう話」
『あー』
「変えられるのは、次の３点」
・配列かそれ以外か。
・各要素の型。
・比較方法。
『あれ？ どっかで見たよおな……』
「 Version 13.06 ( No.242 ) で教えたでしょ」
『あー、そういえば』
「そのときの」
・ソートの早さ。
・安定かどうか。
「はソートアルゴリズムの性質だから変えられないんです」
『だから他の３つを変えるわけね』
「そういうこと。ちなみに、アルゴリズムの性質を決めるのは」
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
「と」
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
「の部分。だから、ここは変えちゃダメだから」
『ってことは他のところを変えるわけね』
「そういうこと。まず、一番変えやすい〈比較方法〉について。比較方法を
変える時には」
if( p_piAry[iIn - 1] > p_piAry[iIn] )
「を変えればいいから」
『 > を < にすると降順になって、 > を >= にすると安定ソートじゃなく
なるんだよね』
「そう。ただ、今火美ちゃんが言ったように、 > を >= にするとアルゴリ
ズムの性質も変わるから、そう考えるとこうした方がいいかも」
// p_iL > p_iR なら true を、
// それ以外は false を返すようにしてください。
bool CompareTo( int p_iL, int p_iR )
{
if( p_iL > p_iR )
{
return true;
}
return false;
}
void DoBubbleSortUseComapre( int *p_piAry, int p_iSize )
{
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// 最後から先頭方向へのループです。
// ただし「入れ替え先」までです。
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
{
if( CompareTo( p_piAry[iIn - 1], p_piAry[iIn] )
== true )
{
// 前の方が大きいので入れ替えます。
int iTemp = p_piAry[iIn];
p_piAry[iIn] = p_piAry[iIn - 1];
p_piAry[iIn - 1] = iTemp;
}
}
}
}
『比較部分を CompareTo() って関数に置き換えたんだね』
「そして、 CompareTo() のコメントでコントラクトします」
『 > の時だけ true ってするわけね。そうすれば == の時は false のはず
だから、常に安定ソートになるわけね』
「そういうこと。他にも、こういうふうに比較部分を関数にすると、次のよ
うなメリットがあります」
・比較方法を簡単に変えられる。
・比較関数を付け替えられる。
「まず〈比較方法を簡単に変えられる〉について。今回は単なるソートだけ
ど、構造体やクラスをソートする時には」
『どの変数をソート対象にするか、とか違うんだもんね。そういうのも関数
に入れておけば簡単に修正できるものね』
「そういうこと。ループ部分から分けられてるから他の部分に影響が出ない
しね。実は、比較方法ってかなりややこしいこと多いから」
『え？ なんか簡単そうだけど』
「渡された変数によって比較する変数を変えたり、計算をしてから比較した
り」
『計算してから……』
「この〈計算〉とかが絡んでくるとかなりややこしくなってくるから、そう
いうことも考えて別関数にするといいかな」
『はーい』
「もうひとつ、〈比較関数を付け替えられる〉は、今は関数を修正する例を
上げたけど」
『それぞれ別に関数を作る？』
「っていう方法もあるから。そうすれば、プログラム的に、呼ぶ関数を変え
るだけで」
『比較方法を変えられる！』
「それに、実行時に呼ぶ関数を変えることもできるから。ソート関数に引数
を追加して、その引数をフラグにしてソート方法を変えるとか」
『そか、比較方法しか違わないんだったら別々の関数作らなくていいんだ
ね』
「そういうこと。それに、 Version 13.01 ( No.237 ) の関数ポインタを使
う方法だってできるから」
『あれって危険なんでしょ？』
「うん、だから強く勧めはしないけど、そういう方法もあるってことで。使
い方そのものはあとで説明するから」
『そなの？』
「ランタイムでソートをする qsort() っていう関数があって、その使い方
を説明するときにね。さて、バリエーションに関しては」
・配列かそれ以外か。
・各要素の型。
「が残っているので次回へ続く！」
『え”』
/*
Preview Next Story!
*/
『結構ボリュームあるんだね』
「今回は欲張ってるからね」
『欲張ってる？』
「たぶん他のアルゴリズムの解説より詳しいと思うよ」
『というわけで次回』
＜ Version 13.10 文字列のソート ＞
「につづく！」
『ってゆーか、それやるからいつまでたっても終わらないんじゃない？』
「う”」
users
users
