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

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

[latexpage]

スポンサーリンク

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

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

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

スポンサーリンク

【手順】昇順ソートの例

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

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

降順ソートの場合は、大小の条件を逆にします。
リストの要素数が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番目の要素を終端とする。
[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の場合、バブルソートでは最速(2周目の繰り返しで交換が一度も発生せずに終了)でも「4(4 – 1)/2=6」回のスキャンが行われます。

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

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

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

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

よって合計は
\begin{eqnarray}
(N-1) + (N-2) + (N-3) + … + 2 + 1 = N(N-1)/2
\end{eqnarray}

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

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

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

詳細記事
1 【Python】バブルソート法(交換法)を実装
おすすめ記事
1 【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2 【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
IPA試験対策
スポンサーリンク

コメント