バブルソート

整列とは、データを昇順もしくは降順に並べ替える処理のことを指します。整列のアルゴリズムには選択ソートや挿入ソート、シェルソート、クイックソートなど様々な種類がありますが、バブルソートは最も基本的な整列のアルゴリズムです。

バブルソートは、隣り合うふたつの要素を比べて、条件に合致すれば要素同士を交換し、これを繰り返していくという手法です。整列する過程で、要素が泡のような動きをすることからバブルソートと呼ばれています。

例えば、「5・3・7・1」という4つの要素を値が小さい順に整列させる場合、まずは一番左の「5」とその隣の「3」を比較しますが、小さい順に並んでいないため「5」と「3」を入れ替えます。

次に、2つ目の要素となった「5」と3つ目の「7」を比較しますが、これは昇順となっているため、入れ替えは発生しません。さらに、3つ目の「7」と4つ目の「1」を比較し、昇順となるように「7」と「1」を入れ替えます。このような手順を踏むことで、一番大きな値である「7」の位置が一番右に決定します。

そして、再び1つ目と2つ目の比較から始め、これを繰り返していくことで、2番目に大きな値の「5」の位置が確定します。このような処理を繰り返していき、入れ替えが一度も発生しなければバブルソートの処理は完了です。

このように、バブルソートは処理が非常にシンプルなので、数ある整列のアルゴリズムの中でも実装が容易というメリットがあります。しかし、処理ステップが多いのがバブルソートのデメリットです。

要素数をnとした場合、バブルソートにおける比較回数はn(n-1)/2で、要素数が多くなるほど処理時間がかかります。例えば、要素数が1000であった場合、499500回の比較が必要で、多くの処理時間がかかります。

そのため、バブルソートは要素数が少ない場合に使用すべきアルゴリズムで、要素数が多い場合は他のアルゴリズムを実装すべきと言えます。