バブルソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[ファイル:Sorting bubblesort anim.gif|視覚化したバブルソート]]
|caption=バブルソートがどのように動作するかの視覚的な説明
|data=[[配列]]
|best-time= <math>O(n)</math>
|average-time= <math>O(n^2)</math>
|time=<math>O(n^2)</math>
|space=<math>O(1)</math> auxiliary 
|optimal=No
}}
'''バブルソート'''（{{lang-en-short|bubble sort}}）は、隣り合う要素の大小を比較しながら整列させる[[ソート]]アルゴリズム。

[[アルゴリズム]]が単純で実装も容易である一方、[[計算複雑性|最悪時間計算量]]は {{math|[[ランダウの記号|O]](''n''<sup>2</sup>)}} と遅いため、一般には[[マージソート]]や[[ヒープソート]]など、より最悪時間計算量の小さな（従って高速な）方法が利用される。

また、[[安定ソート|安定]]な[[ソート#内部ソートと外部ソート|内部ソート]]であり、[[並列計算]]との親和性が高いという利点もある。

'''基本交換法'''、'''隣接交換法'''<ref>[https://dictionary.goo.ne.jp/word/バブルソート/ バブルソートの意味]（出典:デジタル大辞泉）</ref>あるいは単に'''交換法'''とも呼ばれる。「バブルソート」という呼称自体は[[ケネス・アイバーソン]]の1962年の著書 ''“A Programming Language”'' に由来すると考えられる<ref>
{{cite journal
 |first=Owen
 |last=Astrachan
 |title=Bubble Sort -- An Archaelogical Algorithmic Analysis
 |journal=ACM SIGCSE Bulletin
 |volume=35
 |issue=1
 |pages=1&ndash;5
 |issn=0097-8418
 |doi=10.1145/792548.611918
 |date=2003-01-11
 |ref=harv
}}
</ref>。

==アルゴリズム==
[[ファイル:Bubblesort-edited-color.svg|thumb|250px|バブルソートにおける要素の移動例を示した図]]
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行う。なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。

この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ（安定ソート）。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。

例えば前記の特徴によりバブルソートは並列処理と親和性が高く、比較交換器を潤沢に用いることで比較交換順序を調整したハードウェア実装では時間計算量はO(n)になる。この並列処理向けに比較交換順序を調整したアルゴリズムとして[[奇偶転置ソート]]がある。

また特にソフトウェアで実装される場合には一般に先頭から順に順次処理されるものなので、逆に先頭から順に順次処理されることを利用して不要なことが自明な比較交換をしないように効率化することは有効かつ直感的であり、この効率化されたアルゴリズムをもってバブルソートと呼ぶ場合もある。さらに、比較交換順序を逆順にすることで自明な比較交換を検出し易くしたアルゴリズムに[[挿入ソート]]があり、効率化されたバブルソートは簡単な変更で容易に挿入ソートにできることから、ソートのソフトウェア実装としてバブルソートを選択する根拠はなく、学習専用の非効率的なアルゴリズムと考えられているのが現状である。

なお、係る派生したアルゴリズムが''隣接する要素と比較交換''以外の比較や交換を行なうことで効率化を図っている場合、安定という特徴を失う。

以下では、前記の自明な比較交換をしないように効率化されたバブルソートに関して解説する。

要素の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'''

<!--=== PHP で実装 ===
<syntaxhighlight lang="php">
function bubbleSort( &$arr, $asc = true ) {
	$iterations = 0;
	$len = count( $arr );
	$i = 0;
	$ordered = false;
	$newLen = $len;
	while ( !$ordered ) :
		$ordered = true;
		for ( $i = 1; $i < $len; $i++ ) :
			$iterations++;
			$a = $arr[ $i - 1 ];
			$b = $arr[ $i ];
			$comp = (float)( (float)$a - (float)$b );
			if ( ( $asc && $comp > 0 ) || ( !$asc && $comp < 0 ) ) :
			$arr[ $i - 1 ] = $b;
			$arr[ $i ] = $a;
			$ordered = false;
			$newLen = $i;
			endif;
		endfor;
		$len = $newLen;
	endwhile;
	return( $iterations );
}
$arr = array( 4, 4, 3, 2, 4, 5, 88, 3, 8448, 43, 2, 0, 480, 334, 1, 0 );
$iterations = bubbleSort( $arr );
echo( "\nIt took " . $iterations . " iterations to sort the array.\n\n" );
print_r( $arr );
</syntaxhighlight-->

===動作例===
[[ファイル:Bubble-sort-example-300px.gif|thumb|要素の入替え例<br />初期データ: 6 5 3 1 8 7 2 4]]
初期データ: 8 4 3 7 6 5 2 1<br />
　結果が確定した部を太字でしめすと、
{|
|-
| 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

==解析==
[[Image:Bubble sort animation.gif|250px|thumb|ランダム配列数のバブルソートの例]]
「比較回数」は、高々n(n-1)/2回。交換回数は、元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では平均n(n-1)/4回。(''O''(n<sup>2</sup>))

バブルソートでは、大きな数が列の始めに位置していても問題ないが、右図のように列の後のほうに位置している小さな数は列の始めのほうに移動してくるのに時間がかかる。(上述の動作例中の"1"がまさにそのパターン)これを改良するために、[[シェーカーソート]]や[[コムソート]]が提案された。

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist}}

== 関連項目 ==
{{Commonscat|Bubble sort}}
{{ソート}}
[[Category:ソート|はふるそおと]]

[[no:Sorteringsalgoritme#Boblesortering]]