バブルソート 【bubble sort】 単純交換法 / 隣接交換法 / 基本交換法

概要

バブルソート（bubble sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの最も基本的な手法の一つで、端から順番に隣接する要素同士を比較・交換していくもの。

解説 すべての要素について隣接する要素と大きさを比較し、並べたい順番と逆転していたら両者を入れ替える。この手順を最高で要素数-1回繰り返すと並べ替えが完了する。要素の入れ替えが発生しなくなった時点で処理を打ち切ってもよい。

一般的な実装では、この処理を列の一方の端から反対の端まで順番に行うことが多く、繰り返しの度に未整列の要素の中で最も大きな（あるいは小さな）要素が列の端に移動していく様子を泡（バブル）が浮き上がっていく様に例えてこのような名称となった。

最良の場合の計算時間は O（n） と高速だが、最悪の場合の計算時間は O（n²） と整列法の中でも最も遅い部類に入り、平均して高速な手法とは言えない。ただし、要素の比較・交換は順序を問わず並列化しやすいという特徴があり、並列分散処理が可能な環境では高速化することができる。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート（内部ソート）で、同じ大きさの要素の順序が入れ替わらない安定ソートである。アルゴリズムの理解や実装が容易で、コードの記述量が少ない。実用上はあまり使われないが、整列法の学習ではほぼ必ず取り上げられ、効率化した派生アルゴリズムも多く考案されている。