先頭へ戻る

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

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

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

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

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

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

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


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー