バブルソートとは？仕組み・手順・計算量を初心者向けに解説

バブルソートとは？仕組み・手順・計算量を初心者向けに解説

バブルソートとは

バブルソートとは、データの列を左から順に見て、隣り合った2つの要素を比較し、必要なら交換することで整列するアルゴリズムです。小さい順に並べる昇順だけでなく、大きい順に並べる降順にも使えます。

たとえば「5, 2, 8, 1, 9」という数列を昇順にしたい場合、まず5と2を比べます。左の5のほうが大きいので、2つを入れ替えて「2, 5, 8, 1, 9」にします。次に5と8、8と1、8と9というように、隣同士の比較を右へ進めます。

この動きによって、大きな値が少しずつ右側へ押し出されます。泡が水面に上がっていくように見えることから、英語で「Bubble Sort」、日本語では「泡整列」と呼ばれることがあります。

バブルソートの基本的な仕組み

バブルソートの処理は、大きく分けると「比較」「交換」「走査の繰り返し」の3つです。左から右へ向かって隣同士を比べ、左側が右側より大きければ入れ替えます。これを列の末尾まで続けると、その時点で最も大きい値が右端に確定します。

一度右端に移動した最大値は、もうそれ以上右へ移動する必要がありません。そのため、次の走査では右端の要素を比較対象から外し、残った範囲だけを同じように調べます。2回目の走査では2番目に大きい値が右から2番目に移動し、3回目以降も同じ考え方で整列済みの範囲が広がっていきます。

このように、バブルソートは全体を一気に並べ替えるのではなく、小さな比較と交換を積み重ねます。処理の流れが目で追いやすい一方で、データ数が増えるほど比較回数が増えやすい点が特徴です。

具体例で見るバブルソートの手順

具体例として、「5, 2, 8, 1, 9」を昇順に並べ替える流れを見てみましょう。最初の走査では、5と2を比べて入れ替えます。次に5と8は順番通りなのでそのまま、8と1は入れ替え、8と9はそのままです。この時点で列は「2, 5, 1, 8, 9」となり、最大値の9が末尾にあります。

次の走査では、末尾の9を除いた範囲を見ます。2と5はそのまま、5と1は入れ替え、5と8はそのままです。結果は「2, 1, 5, 8, 9」となり、8も正しい位置に近づきます。

さらに残りの範囲で2と1を比べると、1のほうが小さいので入れ替えます。最終的に「1, 2, 5, 8, 9」となり、すべての要素が小さい順に整列されます。重要なのは、各走査で少なくとも1つの値が正しい位置に確定していくことです。

実装するときに押さえる考え方

バブルソートをプログラムで書くときは、多くの場合、二重ループで表現します。外側のループは何回走査するかを管理し、内側のループは隣り合う要素を比較して交換します。比較する範囲は、走査が進むごとに少しずつ短くできます。

もう1つ大切なのが、交換が一度も起きなかった場合の扱いです。ある走査で交換が発生しなければ、その時点で列はすでに整列済みです。そこで交換の有無を記録するフラグを使うと、無駄な走査を省いて早期終了できます。

また、バブルソートは同じ値の順序を保ちやすい「安定ソート」として説明されることがあります。通常は、左側の値が右側の値より大きい場合だけ交換し、同じ値なら交換しないためです。成績や日時など複数の条件で並べ替える考え方を学ぶときにも、この性質は理解しておくと役立ちます。

バブルソートのメリットとデメリット

バブルソートの大きなメリットは、手順が非常に分かりやすいことです。隣り合う値を比較し、順番が逆なら交換するだけなので、配列、ループ、条件分岐、交換処理といったプログラミングの基礎をまとめて学べます。

一方で、実務で大量データを扱う場面では効率の悪さが目立ちます。要素数を n とすると、平均的にも最悪の場合にも計算量はおおむね O(n²) です。要素が10個ならまだ追いやすくても、1000個になると比較回数が非常に多くなります。

つまり、バブルソートは学習用としては優秀だが、大量データの処理には向きにくいアルゴリズムです。少量のデータや、すでにほぼ整列済みのデータを早期終了付きで扱う場合には理解しやすい選択肢になりますが、速度が重要な処理では別のソートを検討するのが一般的です。

他の整列アルゴリズムとの違い

整列アルゴリズムには、バブルソート以外にも多くの種類があります。たとえばクイックソートは基準値を使ってデータを分割しながら整列し、マージソートは小さく分けた列を整列済みの状態で併合していきます。どちらもバブルソートより考え方は複雑ですが、大量データでは高速に動作しやすい手法です。

選択ソートや挿入ソートも、バブルソートと同じく入門でよく扱われます。選択ソートは未整列の範囲から最小値を選んで先頭へ置く方法、挿入ソートは手札を並べるように適切な位置へ要素を差し込む方法です。バブルソートは、この中でも特に「隣接する要素の交換」に注目した手法だと考えると理解しやすくなります。

実際の開発では、多くの言語に用意されている標準のソート機能を使うことが一般的です。それでもバブルソートを学ぶ価値があるのは、比較、交換、ループ、計算量というアルゴリズムの基礎を、最小限の仕組みで確認できるからです。

バブルソートを学ぶときの注意点

初心者がつまずきやすいのは、「1回の走査で全体が完全に整列する」と考えてしまう点です。実際には、1回の走査で確定するのは主に末尾側の1要素です。残りの範囲は、何度も走査して少しずつ整えていきます。

また、「単純で分かりやすい」ことと「速い」ことは同じではありません。バブルソートは構造が見えやすいので学習に向いていますが、実務で大量のデータを並べ替えるときは、標準ライブラリやより効率的な整列アルゴリズムを使う判断が必要です。

学習では、まず紙に数列を書き、隣同士の比較と交換を手で追ってみると理解が深まります。その後にコードへ移すと、外側のループ、内側のループ、交換処理、早期終了の意味がつながりやすくなります。

まとめ

バブルソートは、隣り合う要素を比較し、順番が逆なら交換する処理を繰り返してデータを整列するアルゴリズムです。大きな値が右端へ移動していく様子が泡のように見えるため、この名前で呼ばれます。

仕組みが単純で実装しやすいため、整列アルゴリズムの入門には適しています。一方で、計算量は O(n²) になりやすく、データ数が多い処理には向きません。バブルソートを学ぶときは、手順の分かりやすさだけでなく、なぜ遅くなりやすいのか、他のソートと何が違うのかまで確認すると理解が広がります。

更新履歴