バブルソートとは
バブルソート（Bubble Sort / 交換法）とは、データ群を並べ替えるソートアルゴリズムの一種で、隣り合う2つのデータの大小を比較し、順序が逆であれば入れ替えるという操作を、配列の端から順に繰り返す方法です。この操作を繰り返すと、軽い（値が小さい）要素が徐々に上に上がり、重い（値が大きい）要素が底へ沈むように並び替わります。泡（バブル）が浮かび上がってくる様子に似ていることから名付けられました。
具体例
バラバラに並んだ「5, 3, 8, 2」を昇順にする際、まず隣の5と3を比較して入れ替え「3, 5, 8, 2」とし、次に5と8はそのまま、最後に8と2を比較して入れ替え「3, 5, 2, 8」とする。これを繰り返して全体を整列させます。
// バブルソートの入れ替えのイメージ
[5, 3, 8, 2] --> 5と3を比較して交換
[3, 5, 8, 2] --> 5と8を比較してそのまま
[3, 5, 8, 2] --> 8と2を比較して交換
[3, 5, 2, 8] --> 1周目の終わり（最大値の8が右端に移動した）もう少し詳しく
バブルソート（Bubble Sort）は、別名「交換法」とも呼ばれる、最もシンプルで直感的な整列（ソート）アルゴリズムの一つです。処理の基本は、配列の端（例えば末尾）から隣り合う要素同士を比較し、順序が逆（昇順ソートであれば、左 > 右）の場合にその2つを入れ替える（スワップする）という操作です。これを配列の先頭に向かって繰り返していくと、1周（1パス）終わった時点で、配列内の最小値（または最大値）が一番端（先頭）に「泡（バブル）が浮かび上がるように」移動して確定します。このパスを、確定していない残りの要素に対して繰り返すことで、全体を整列させます。実装は非常に容易ですが、データ数をNとしたとき、比較回数は常に N(N-1)/2 回となり、最悪および平均の時間計算量は O(N^2) となります。データ数が増えると著しく処理時間が長くなるため、実用的なプログラムで大規模なデータをソートする用途には適していません。一方で、同じ値の要素の前後関係がソート前後で変化しない「安定ソート」であるという性質を持っています。
試験でのポイント
試験では、バブルソートの時間計算量が O(N^2) であることや、具体的な配列データを与えられて「パスを1回（あるいは数回）実行した後の配列の状態はどうなっているか」をトレースさせる問題が出題されます。また、すでにデータが整列済みである場合に余計なループをスキップする「フラグ（交換が発生したかどうかを記録する変数）を用いた最適化バブルソート」のアルリズム構造についても出題されることがあります。
関連する用語
スワップ（2つの変数の値を入れ替える基本処理）、時間計算量 O(N^2)（データの2乗に比例して処理時間が増大する効率の悪いオーダー）、安定ソート（元の順序を崩さずにソートを行うアルゴリズムの分類）。