バブルソート | Programming Place Plus　用語集

名称

• バブルソート　【bubble sort】
• (同義) 隣接交換法
• (同義) 基本交換法
• (同義) 単純交換法

解説

ソートのアルゴリズムの一種で、データ列内の隣接する２つの要素の大小関係の比較と交換を、必要な回数だけ繰り返すことによって、ソートを行う手法です。

データ列内のすべての要素に対して、その隣接要素との比較を行い、大小関係が目的の順序の逆になっていたら交換するという処理を行います。この過程が終わるたびに、最小値（あるいは最大値）である要素が、データ列の端に移動してきます。この様子を、泡が浮き上がってくるさまに見立てて、バブルソートと呼ばれます。この過程を、最大で要素数-1回だけ繰り返すと全体のソートが完了します（過程の中で交換が発生しなくなったら、打ち切って構わない）。

最悪時の計算量が O(n²) であり、これはソートアルゴリズムとしては遅いものであるといえます。安定ソートであり、内部ソートです。

並列化しやすいという長所があるほか、いくつか改良されたアルゴリズムもあります（コムソート、シェーカーソートなど）。

バブルソートの解説がアルゴリズムとデータ構造編【整列】第３章にあります。