バブルソート
整列 バブルソート、選択ソートの演習
バブルソートは選択ソートと並んで基本的な整列アルゴリズムであり、計算量は O(N^2) で選択ソートと同等である。
基本的な手順はつぎのとおり。右から大きい順に並べる。
左端をスタートにして隣同士二つを比べ、より大きなほうを右になるように置き換える。（右が大きければそのまま。）
一つ右に移動して同じことをする
この二つを繰り返し右端での比較交換が終わると一番大きなものが右端に寄る
また左端に戻り、上記３つを何度か繰り返すと全体が整列する
例
3241 -(左端の3,2比較)-> 2341 -(3,4比較)-> 2341 -(4,1比較)-> 2314 -(左端に戻って 2,3 比較)-> 2314 -(3,1比較)-> 2134 -(左端に戻って 2,1比較)-> 1234 終わり
配列a[10]を整列するプログラムの断片
code:bubblesortpart.c
for(j=0; j<10-1; j++){
for(i=0; i<10-1; i++){
}
}
}
クイズ
繰り返しの上限が i<10-1 となっているのはなぜだろうか
i の繰り返しを j の繰り返しの中で毎度10回行っているが、必要だろうか？
（例では左端に戻るたびに回数が減っている）
i の繰り返しを減らすことができるが、データの個数 N に対する計算量 O(N^2) に変化はあるだろうか？
演習
1) 選択ソートのプログラム（sortselectloop.c）を参考にしてバブルソートするプログラムを書こう。 2) ソートするデータ数を 10、100、1000、10000 などと変更し、計算時間を考察しよう。