Version 13.08
バブルソートのコーディング
「今回は、前回説明したバブルソートを実際にコーディングしてみます」
『それって結構難しそう』
「かもね。アルゴリズムは、頭ではわかってても実際にコードにするとうま
くいかないことが結構あるから」
『とりあえず作っていって慣れないとね』
「そうだね。まず、バブルソートのおさらいから」
4 9 3 5 8
「こう数字が並んでいる場合。右から２つずつ見ていって、左の方が大きか
ったら入れ替える、ってしていきます」
4 9 3 5 8 → 4 9 3 5 8
^ ^ ^ ^
4 9 3 5 8 → 4 9 3 5 8
^ ^ ^ ^
4 9 3 5 8 → 4 3 9 5 8
^ ^ ^ ^
4 3 9 5 8 → 3 4 9 5 8
^ ^ ^ ^
「こうすることで、一番左に〈一番小さい数〉が来るようになります。で、
２周目」
3 4 9 5 8 → 3 4 9 5 8
^ ^ ^ ^
3 4 9 5 8 → 3 4 5 9 8
^ ^ ^ ^
3 4 5 9 8 → 3 4 5 9 8
^ ^ ^ ^
『一番左まで見ないんだね』
「一番左にはもう〈一番小さい数〉が来てるからね。これで、左から二番目
に〈二番目に小さな数〉が来ました。３周目はこう」
3 4 5 9 8 → 3 4 5 8 9
^ ^ ^ ^
3 4 5 8 9 → 3 4 5 8 9
^ ^ ^ ^
「同じく４周目はこう」
3 4 5 8 9 → 3 4 5 8 9
^ ^ ^ ^
『こうやって見ていくと簡単だよね』
「そう、これだけならね」
『そか、これをコードに落とすのが大変なんだ……』
「そういうこと。じゃあ、ひとつずつ見ていこうか。まずはこの部分」
4 9 3 5 8
~ ^
4 9 3 5 8
~ ^
4 9 3 5 8
~ ^
4 3 9 5 8
~ ^
「わかりにくくなるから、入れ替える部分は削除しました。それと、両方 ^
だとわかりにくいから、左は ~ にしてみました」
『右から左に見ていくんだよね』
「だから、配列だと後ろから見ていくことになります」
『うしろ……』
「今回は要素の数が５つ、だから配列のサイズは 5 」
int iAry[5];
「その場合、配列の一番後ろは」
iAry[4] = 8;
『サイズから 1 引けばいいんだね』
「配列は 0 から始まるからね」
『右端が 4 で、左端は 0 ね』
「ちょっと待って、その辺注意しないといけないから」
『え？』
4 9 3 5 8
~ ^
「このとき、 ~ は iAry[3] で、 ^ は iAry[4] に当たるでしょ」
『そだね』
「この ~ と ^ の値は、右から左に移るに従って」
^ : 4 3 2 1
~ : 3 2 1 0
「というふうに減っていきます」
『あ…… ^ は 1 までしかいかないし、~ は 3 からなんだね』
「これをきっちりとした言葉で書くと」
^ : 配列の最後から、先頭 - 1 まで。
~ : ^ - 1
『あ、 ~ は ^ から 1 引いたの、でいいんだ 』
「これができるのは、 ^ が 0 まで行かないからだからね」
『行ったら iAry[-1] ではみ出ちゃう……』
「そういうこと。この部分だけプログラムで書くと、こうなります」
// p_piAry : 配列。
// p_iSize : 配列のサイズ。
for( int iIn = p_iSize - 1; 0 < iIn; iIn-- )
{
if( p_piAry[iIn - 1] > p_piAry[iIn] )
{
// 前の方が大きいので入れ替えます（実装はあとで）。
}
}
『 for で、配列の最後から…… 0 < iIn 、だから 0 まで行かないんだ
ね。入れ替えのチェックは iIn と iIn - 1 、つまりさっきのだと ~ と ^
で比較して、 ~ の方が大きかったら入れ替え……』
「そういうこと。基本的に、配列をひとつずつ見ていくときには for を使
えばいいから」
『入れ替え部分は？』
「それは簡単にできるからあとで。説明も必要ないし。それよりも、 if の
条件の方が重要かも。もしこれを」
if( p_piAry[iIn - 1] >= p_piAry[iIn] )
「ってしたらどうなると思う？」
『 = が付いただけだよね。でも同じだったら入れ替えても関係ないんじ
ゃ……あ、安定ソートにならない？』
「そういうこと。 = を付けると安定ソートじゃなくなるんです。今回の例
では関係ないけど、配列の要素が構造体やクラスの場合には」
『安定ソートかそうじゃないか、って大きいもんね』
「そういうこと。それともうひとつ」
if( p_piAry[iIn - 1] < p_piAry[iIn] )
『 > が < になった』
「こうすると降順、つまり大きい順に並びます」
『逆になるんだ……』
「つまり、この【条件式】はとても重要。これをちょっと間違えるだけで並
び方が全然違います」
『ちょっと怖いね……』
「一番いいのは、この条件文を関数化して、チェック用のテストも作ること
かな」
『そうすれば確実だもんね』
「それに、関数化しておけば、あとから付け替える時に便利だからね。昇順
と降順を変えることとか」
『多そうだもんね。それが関数切り替えるだけでできるなら楽だよね』
「そういうこと。ま、今回はこのままで。さて、ここまでは〈１周目〉につ
いて見てきました」
『そういえば、それがあと３回あるんだよね』
「そう。そこで、各周の最後だけ並べてみます」
4 3 9 5 8 ←１周目最後
^ ^
3 4 5 9 8 ←２周目最後
^ ^
3 4 5 8 9 ←３周目最後
^ ^
3 4 5 8 9 ←４周目最後
^ ^
『これは左から右に移動してるんだね……』
「このあたりの考え方はいくつかあるんだけど、一番簡単なのは〈入れ替え
先〉を考えることかな」
『入れ替え先？』
「各周で、一番小さな数を入れておく場所があるでしょ」
『１周目が 0 番目で、２周目が 1 番目で、ってゆーのね。そか、それが 1
ずつ増えていくから』
「それを for ループにすればいいわけ。一番右端は見ないから、配列のサ
イズ - 2 までループすればいいから、こうなります」
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// この中にさっきのループを入れます。
}
『あれ？ 中の条件って iOut <= p_iSize - 2 の方がよくない？』
「その辺は好みかな。僕は for の条件式は〈止まるところ + 1 〉に決めて
るから」
『なんで？』
「 for ループの代わりに使える STL っていうライブラリがあって、それが
この方法で統一されてるから」
『私もそうした方がいい？』
「ってこともないと思うよ。今は〈自分にとってわかりやすい方法〉で書く
ことが重要だから」
『まだ初心者ってことね』
「う”、そういうわけじゃないけど……じゃ、今回の関数をまとめてみま
す」
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;
}
}
}
}
『おー』
「というわけで次回に続く！」
『ええっ！？』
/*
Preview Next Story!
*/
『完成したら終わりじゃないの？』
「それじゃ、本当にこの形でしか使えないでしょ」
『この形？』
「 int の配列で、普通の比較でのソート」
『つまり、 int 以外で、特殊な比較ができないとだめ？』
「そういうこと」
『というわけで次回』
＜ Version 13.09 ソートの中身のバリエーション ＞
「につづく！」
『応用力付けなきゃ意味ないもんね』
「本当に使えるプログラムじゃなきゃ意味ないからね」
users
users
