【バブルソート法（交換法）とは】リストの昇順・降順ソートと計算量

バブルソート法（交換法）とは？リストを昇順・降順ソートする手順について解説します。

【バブルソートとは】リストを昇順・降順ソート

バブルソート法（交換法）は、リストの隣接する２つの要素の値を順に比較し、大小関係が指定した条件を満たしていない場合に、交換を行うアルゴリズムです。
交換が一度も行われなくなったときに処理を終了し、そのときのリストが整列（ソート）されます。

値が大きい、もしくは小さい要素が浮かびあがってくることから、バブル(bubble:泡)ソートと呼ばれます。

【手順】昇順ソートの例

バブルソート法で昇順ソートする場合の手順は以下のとおりです。

順序	操作
①	1番目の要素と、隣接する2番目の要素の値を比較する。1番目の値の方が大きければ、要素の値を交換する。
②	2番目の要素と、隣接する3番目の要素の値を比較する。2番目の値の方が大きければ、要素の値を交換する。
③	終端要素nまで２つの要素の比較と交換を繰り返す。
④	終端の要素には、最も大きい値が格納されるので、比較と交換を行う終端位置を１つ減らす。
⑤	交換が一度も生じなくなるまで手順①〜③を繰り返す。

降順ソートの場合は、大小の条件を逆にします。
リストの要素数がnの場合、バブルソートでは必ず「n(n – 1)/2」回のスキャンが行われます。
リストの個数が多くなればなるほど処理速度も遅くなりますが、シンプルなアルゴリズムなのでデータ量が少ないときには手軽に実装できます。

【計算例】昇順ソート

理解を深めるために、4つの要素をもつリスト[5, 3, 8, 2]の昇順ソートをバブルソート法で行ってみます。

リストの状態	操作
[5, 3, 8, 2]	1番目の要素と、隣接する2番目の要素の値を比較する。
[3, 5, 8, 2]	1番目の値の方が大きいので、要素の値を交換する。
[3, 5, 8, 2]	2番目の要素と、隣接する3番目の要素の値を比較する。
[3, 5, 8, 2]	2番目の値の方が小さいので、交換は行わない。
[3, 5, 8, 2]	3番目の要素と、隣接する4番目（終端）の要素の値を比較する。
[3, 5, 2, 8]	4番目（終端）の値の方が大きいので、要素の値を交換する。
[3, 5, 2, 8]	4番目（終端）の要素には、最も大きい値が格納されるので、次のスキャンは３番目の要素を終端とする。
[3, 5, 2, 8]	1番目の要素と、隣接する2番目の要素の値を比較する。
[3, 5, 2, 8]	2番目の値の方が小さいので、交換は行わない。
[3, 5, 2, 8]	2番目の要素と、隣接する3番目の要素の値を比較する。
[3, 2, 5, 8]	2番目の値の方が大きいので、要素の値を交換する。
[3, 2, 5, 8]	3番目（終端）の要素には、最も大きい値が格納されるので、次のスキャンは2番目の要素を終端とする。
[3, 2, 5, 8]	1番目の要素と、隣接する2番目の要素の値を比較する。
[2, 3, 5, 8]	1番目の値の方が大きいので、要素の値を交換する。
[2, 3, 5, 8]	2番目（終端）の要素には、最も大きい値が格納されるので、次のスキャンは1番目の要素を終端とする（これ以上交換はできないので、ここで終了）。

このように、リストの要素数が4の場合、バブルソートでは最速（２周目の繰り返しで交換が一度も発生せずに終了）でも「4(4 – 1)/2=6」回のスキャンが行われます。

【計算コスト】バブルソートに要する時間量

バブルソートの処理は、2つのデータの入れ替えを何回繰り返すかによって、ソートに要する時間量を評価できます。

リストの要素数（データ数）がNの場合、次のようになります。

操作	入れ替え回数
最大値のデータを一番下まで移動	N-1 回
2番目のデータを下から2番目まで移動	N-2 回
3番目のデータを上から3番目まで移動	N-3 回
：	：
N-1番目のデータを下から2番目まで移動	1回

よって合計は

(1)  

となり、Nの2乗が含まれているため、オーダーはとなります。
つまり、データ量が2倍に増えると、並べ替えに要する時間は4倍に増大します。

【プログラミング】バブルソートの実装

プログラミング言語でバブルソートを実装する方法については、言語別に下記事で紹介しています。

–	詳細記事
1	【Python】バブルソート法（交換法）を実装

–	おすすめ記事
1	■【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2	■【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験