バブルソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
バブルソートは、ソートのアルゴリズムの一つ。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。
バブルソートを高速化したソート法として、シェーカーソートやコムソートが知られている。
[編集] アルゴリズム
1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。
[編集] 動作例
初期データ: 8 4 3 7 6 5 2 1
- 結果が確定した部を太字でしめすと、
- 4 3 7 6 5 2 1 8 （1回目の外側ループ終了時）
- 3 4 6 5 2 1 7 8 （2回目の外側ループ終了時）
- 3 4 5 2 1 6 7 8 （3回目の外側ループ終了時）
- 3 4 2 1 5 6 7 8 （4回目の外側ループ終了時）
- 3 2 1 4 5 6 7 8 （5回目の外側ループ終了時）
- 2 1 3 4 5 6 7 8 （6回目の外側ループ終了時）
- 1 2 3 4 5 6 7 8 （7回目の外側ループ終了時）
[編集] 計算時間
「比較回数」は、n(n-1)/2回。交換回数は、元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では約n2/2回。
