読者です 読者をやめる 読者になる 読者になる

バブルソート

基礎プロや応プロでバブルソートを習うと思うのだけど,

どうもコードの丸暗記が多くて,記憶が曖昧だったりして,

いつまでたっても正しいコードをかけない学生がいる.

バブルソート程度なら,とりあえず考え方を押さえておけば書けるはず.

 

バブルソートは「隣り合う要素の大小関係を比較して並び替えて行く」

ということが基本的な考え方.

例えば,「4,7,3,9,2」という列を昇順(小さい要素から大きな要素の順)にソートすると,

4 7 3 9 2 (配列だと0番目と1番目を比較)

4 7 3 9 2 (配列だと1番目と2番目を比較)

4 3 7 9 2 (配列だと2番目と3番目を比較)

4 3 7 9 2 (配列だと3番目と4番目を比較)

4 3 7 2 9

と隣合う要素を比較して,手前が大きければ入れ替えるという操作を行う.

この操作で,1番大きな要素の「9」は一番後ろにくる.

2巡目は,

4 3 7 2 9

3 4 7 2 9

3 4 7 2 9

3 4 2 7 9

3巡目は,

3 4 2 7 9

3 4 2 7 9

3 2 4 7 9

4巡目は,

3 2 4 7 9

2 3 4 7 9

となり,ソートが完了する.

 

各巡で行っていることは,「隣の要素を比較して交換する」ということだけなので,

listを配列,swapを要素を交換する関数とすると,上の各巡回は,

for(int j=0; j<=4-(今の巡回数); j++){ 

    if( list[j] > list [j+1] ) swap( list[j], list[j+1]);

}

とコードを書くことができる.

jの範囲で迷うかもしれないが,各巡回で最後に比較する要素は,

1巡目:配列の3番目と4番目

2巡目:配列の2番目と3番目

3巡目:配列の1番目と2番目

4巡目:配列の0番目と1番目

となるので,jは0から4-(巡回数)の範囲で動けばいいことがわかる.

 

あとは,巡回数が4回であることに注意すると,

上の作業を繰り返せばいいだけなので,

for(int i=1; i<=4; i++){

 for(int j=0; j<=4-i; j++){ // 4-(各巡回数)= 4-i

     if( list[j] > list [j+1] ) swap( list[j], list[j+1]);

 }

}

と完成する.

 

このままだと要素数が5にしか対応できないので,どんなサイズにでも対応できるようにしよう.

今,配列のサイズをnと置くことにする.

サイズに関係するところは,赤字になっていることは簡単にわかるはず.

for(int i=1; i<=4; i++){

 for(int j=0; j<=4-i; j++){

     if( list[j] > list [j+1] ) swap( list[j], list[j+1]);

 }

}

あとは,どう書き換えるかであるが,外側は簡単で,

例を見ればわかるように,配列のサイズ-1回の巡回を行えばいいので,

for(int i=1; i<=n-1; i++){

 for(int j=0; j<=4-i; j++){

     if( list[j] > list [j+1] ) swap( list[j], list[j+1])

 }

}

となることがわかる.では内側は?

例に戻ると,各巡回において,最後の要素の比較が,

1巡目:配列の3番目と4番目

2巡目:配列の2番目と3番目

3巡目:配列の1番目と2番目

4巡目:配列の0番目と1番目

というようになっていることから,一般化すると,

i巡目:配列のn-i-1番目とn-i番目

となることがわかる.実際にn=5を入れると正しいことが確認できるだろう.

ということで,最終的に,

for(int i=1; i<=n-1; i++){

 for(int j=0; j<=n-i-1; j++){

     if( list[j] > list [j+1] ) swap( list[j], list[j+1]);

 }

}

となって昇順のバブルソートのコードが完成する.

 

コードを書く時に必要なことは,(できる人は別として)具体的な例題を考えて,

まずは,どうすれば問題が解けるかを考える.

そのあとは,具体的なケースでいいので,それで動くコードを書いてみる.

最後に一般化するということを行えば,少しはミスを減らすことができると思う.

ただ,もちろん特殊なケースを考えることが必要になったりすることもあるので,

全てがこの方法で解決できるわけではないが,

何もわからない状態で,いきなり一般化したプログラムを書くというのは,あまり得策ではない.