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

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

[latexpage]

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

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

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

【手順】昇順ソートの例

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

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

【計算例】昇順ソート

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

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

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

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

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

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

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

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

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