バブルソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
バブルソートは、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。
目次 |
[編集] アルゴリズム
1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。
procedure bubbleSort( A : list of sortable items ) defined as:
for each i in 1 to length(A) - 1 do:
for each j in 2 to length(A) - i + 1 do:
if A[ j ] < A[ j - 1 ] then
swap( A[ j ], A[ j - 1 ] )
end if
end for
end for
end procedure
[編集] 動作例
初期データ: 8 4 3 7 6 5 2 1
結果が確定した部を太字でしめすと、
| 4 | 3 | 7 | 6 | 5 | 2 | 1 | 8 | （1回目の外側ループ終了時 交換回数:7） |
| 3 | 4 | 6 | 5 | 2 | 1 | 7 | 8 | （2回目の外側ループ終了時 交換回数:5） |
| 3 | 4 | 5 | 2 | 1 | 6 | 7 | 8 | （3回目の外側ループ終了時 交換回数:3） |
| 3 | 4 | 2 | 1 | 5 | 6 | 7 | 8 | （4回目の外側ループ終了時 交換回数:2） |
| 3 | 2 | 1 | 4 | 5 | 6 | 7 | 8 | （5回目の外側ループ終了時 交換回数:2） |
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | （6回目の外側ループ終了時 交換回数:2） |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | （7回目の外側ループ終了時 交換回数:1） |
交換回数の合計:7+5+3+2+2+2+1=22
[編集] 解析
「比較回数」は、n(n-1)/2回。交換回数は、元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では平均n(n-1)/4回。
バブルソートでは、大きな数が列の始めに位置していても問題ないが、右図のように列の後のほうに位置している小さな数は列の始めのほうに移動してくるのに時間がかかる。(動作例中の"1"がまさにそのパターン)これを改良するために、シェーカーソートやコムソートが提案された。
