#pragma twice

KAB-studio > プログラミング > #pragma twice > 244 Version 13.08 バブルソートのコーディング

#pragma twice 244 Version 13.08 バブルソートのコーディング

前のページへ 表紙・目次へ 次のページへ

 Version 13.08
バブルソートのコーディング

今回は、前回説明したバブルソートを実際にコーディングしてみます
それって結構難しそう
かもね。アルゴリズムは、頭ではわかってても実際にコードにするとうま
くいかないことが結構あるから
とりあえず作っていって慣れないとね
そうだね。まず、バブルソートのおさらいから

4 9 3 5 8 

こう数字が並んでいる場合。右から2つずつ見ていって、左の方が大きか
ったら入れ替える、ってしていきます

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 
^ ^          ^ ^

こうすることで、一番左に〈一番小さい数〉が来るようになります。で、
2周目

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周目はこう

3 4 5 9 8 → 3 4 5 8 9 
      ^ ^          ^ ^
3 4 5 8 9 → 3 4 5 8 9 
    ^ ^          ^ ^

同じく4周目はこう

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つ、だから配列のサイズは 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] )

 > が < になった
こうすると降順、つまり大きい順に並びます
逆になるんだ……
つまり、この【条件式】はとても重要。これをちょっと間違えるだけで並
び方が全然違います
ちょっと怖いね……
一番いいのは、この条件文を関数化して、チェック用のテストも作ること
かな
そうすれば確実だもんね
それに、関数化しておけば、あとから付け替える時に便利だからね。昇順
と降順を変えることとか
多そうだもんね。それが関数切り替えるだけでできるなら楽だよね
そういうこと。ま、今回はこのままで。さて、ここまでは〈1周目〉につ
いて見てきました
そういえば、それがあと3回あるんだよね
そう。そこで、各周の最後だけ並べてみます

4 3 9 5 8 ←1周目最後
^ ^      
3 4 5 9 8 ←2周目最後
  ^ ^    
3 4 5 8 9 ←3周目最後
    ^ ^  
3 4 5 8 9 ←4周目最後
      ^ ^
これは左から右に移動してるんだね……
このあたりの考え方はいくつかあるんだけど、一番簡単なのは〈入れ替え
先〉を考えることかな
入れ替え先?
各周で、一番小さな数を入れておく場所があるでしょ
1周目が 0 番目で、2周目が 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 ソートの中身のバリエーション >
につづく!
応用力付けなきゃ意味ないもんね
本当に使えるプログラムじゃなきゃ意味ないからね
 
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
RSSに登録
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
 
このページは、Visual C++ 6.0を用いた C++ 言語プログラミングの解説を行う#pragma twiceの一コンテンツです。
詳しい説明は#pragma twiceのトップページをご覧ください。