EN
JP
KRBubble SortをJavaScriptで実装する方法｜仕組み・コード例・計算量を解説
Bubble Sortは、ソートアルゴリズムの中でも特に基本的な手法としてよく紹介されるアルゴリズムです。日本語ではバブルソートと呼ばれ、隣り合う要素を比較し、順序が逆であれば交換する処理を繰り返すことで、配列全体を並び替えます。JavaScriptでアルゴリズムを学び始めるとき、Bubble Sortは処理の流れが目で追いやすく、比較、交換、ループといった基本的な考え方を理解するのに適しています。配列の中で値が少しずつ移動していく様子を確認しやすいため、初心者にとって最初のソート実装として扱いやすい方法です。
ただし、Bubble Sortは効率の良いソートアルゴリズムではありません。平均ケースや最悪ケースでは時間計算量がO(n^2)となり、要素数が増えるほど処理が急激に重くなります。そのため、実務で大量のデータを並び替える場合には、JavaScript標準のArray.prototype.sort()を使うのが一般的です。それでもBubble Sortを学ぶ意味は十分にあります。なぜなら、ソートの基本構造、二重ループの負荷、交換処理の仕組み、早期終了による簡単な最適化など、アルゴリズム学習で重要な要素をまとめて理解できるからです。本記事では、Bubble Sortの仕組み、JavaScriptでの実装方法、最適化、計算量、実務での位置づけまで詳しく解説します。
1. Bubble Sortとは？
Bubble Sortとは、配列の隣り合う要素を順番に比較し、並び順が逆であれば交換するソートアルゴリズムです。昇順に並べる場合、左側の値が右側の値より大きければ交換します。この処理を配列の先頭から末尾まで繰り返すと、1回の走査ごとに大きな値が後ろへ移動していきます。大きな値が泡のように浮かび上がっていくように見えることから、Bubble Sortという名前が付いています。処理の考え方は非常に単純で、配列の状態がどのように変化するのかを追いやすい点が特徴です。
Bubble Sortは、実装が簡単な一方で、効率面ではあまり優れていません。隣接要素を何度も比較し、必要に応じて交換するため、データ量が増えると比較回数と交換回数が多くなります。特に、逆順に近い配列を昇順に並べる場合、多くの交換が必要になります。そのため、実務で大量データを処理する目的には向いていません。しかし、アルゴリズム学習では、どのように配列が並び替えられるのか、二重ループがなぜ重くなりやすいのかを理解するうえで非常に役立ちます。
1.1 Bubble Sortの基本イメージ
たとえば、[5, 3, 8, 1]という配列を昇順に並べたいとします。最初に5と3を比較すると、5の方が大きいため交換します。次に5と8を比較すると、5は8より小さいためそのままです。次に8と1を比較すると、8の方が大きいため交換します。この1回目の走査が終わった時点で、最大値である8は配列の末尾に移動しています。次の走査では、残りの範囲に対して同じように隣接要素の比較と交換を行います。
このようにBubble Sortでは、1回の走査ごとに少なくとも末尾側の要素が正しい位置に近づいていきます。配列全体を何度も走査する必要はありますが、処理の流れは非常に分かりやすいです。学習時には、紙に配列を書いて、比較される2つの値と交換後の状態を順番に追ってみると理解が深まります。Bubble Sortは、ソートアルゴリズムの効率を学ぶ前に、まず「比較して並べ替える」という基本動作を体感するのに適したアルゴリズムです。
1.2 Bubble Sortの特徴
Bubble Sortの最大の特徴は、実装が簡単で理解しやすいことです。複雑なデータ構造や再帰処理を使わず、配列、ループ、条件分岐、交換処理だけで実装できます。そのため、JavaScriptでアルゴリズムを学び始めたばかりの人でも、コードを読みながら処理の流れを追いやすいです。隣接要素を比較して交換するという動きは直感的であり、ソート処理の基本を学ぶうえで分かりやすい教材になります。
一方で、Bubble Sortは処理効率が低いという欠点があります。基本実装では、配列がほとんど整列されている場合でも、決められた回数の比較を行ってしまいます。また、要素数が増えると二重ループによって比較回数が大きく増加します。そのため、Bubble Sortは実務で大きなデータを扱うためのアルゴリズムというより、学習用のアルゴリズムとして理解するのが適切です。標準のsort()メソッドと比較することで、なぜ効率的なアルゴリズムが必要なのかも理解しやすくなります。
1.3 学習する意味
Bubble Sortを学ぶ意味は、単に一つのソート方法を覚えることではありません。配列の要素をどのように比較するのか、交換処理で値がどのように移動するのか、二重ループによって処理回数がどのように増えるのかを理解することに価値があります。JavaScriptの標準sort()を使えば簡単に並び替えはできますが、内部で行われる比較の考え方を理解していないと、比較関数の設計でつまずきやすくなります。
また、Bubble Sortを実装してみることで、アルゴリズムの改善について考えるきっかけにもなります。たとえば、すでに配列が整列されている場合でも最後まで処理するのは無駄です。この無駄を減らすために、交換が発生したかどうかを記録して早期終了するという最適化を加えられます。このように、まず単純な実装を理解し、その後で改善点を考える流れは、プログラミング全般の学習にもつながります。
2. JavaScriptでBubble Sortを実装する
Bubble SortをJavaScriptで実装するには、基本的に二重ループを使います。外側のループは配列全体を何回走査するかを管理し、内側のループは隣り合う要素を順番に比較します。昇順に並べる場合は、左側の値が右側の値より大きいときに交換します。1回の外側ループが終わるたびに、末尾側の要素が正しい位置に確定していくため、内側のループの範囲を少しずつ短くできます。
実装時に考えるべきポイントは、元の配列を直接変更するかどうかです。学習用のコードでは元配列を直接変更しても構いませんが、実務では元データを保持したい場面が多いため、コピーを作ってからソートする方が安全です。この記事では、元の配列を壊さないようにスプレッド構文でコピーを作り、そのコピーに対してBubble Sortを実行します。この方法により、関数の外側にある元データに影響を与えずに、ソート済みの配列を返すことができます。
2.1 基本実装
以下は、数値配列を昇順に並べるBubble Sortの基本実装です。bubbleSort関数は引数として配列を受け取り、まず[...numbers]でコピーを作成します。その後、外側のfor文で走査回数を管理し、内側のfor文で隣接要素を比較します。もしresult[j]がresult[j + 1]より大きければ、2つの値を入れ替えます。これを繰り返すことで、配列全体が昇順に整列されます。
このコードで重要なのは、内側のループ条件がresult.length - 1 - iになっている点です。外側のループが1回進むたびに、末尾側の要素は正しい位置に確定していきます。そのため、すでに確定した末尾部分を再度比較する必要はありません。- iを使うことで、無駄な比較を少し減らしています。Bubble Sortの基本構造を理解するときは、外側のループが「何周するか」、内側のループが「どの範囲を比較するか」を分けて考えると分かりやすいです。
function bubbleSort(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { for (let j = 0; j < result.length - 1 - i; j++) { if (result[j] > result[j + 1]) { const temp = result[j]; result[j] = result[j + 1]; result[j + 1] = temp; } } } return result;}console.log(bubbleSort([5, 3, 8, 1])); // [1, 3, 5, 8]
2.2 交換処理を分かりやすくする
Bubble Sortでは、隣り合う2つの値を交換する処理が中心になります。基本実装では、一時変数tempを使って交換しています。これは、片方の値を上書きして失わないようにするためです。まずresult[j]をtempに保存し、次にresult[j]へresult[j + 1]を代入し、最後にresult[j + 1]へtempを代入します。この流れを理解しておくと、配列内の値を安全に入れ替える方法が分かります。
JavaScriptでは、分割代入を使って交換処理を短く書くこともできます。[result[j], result[j + 1]] = [result[j + 1], result[j]]のように書けば、一時変数を用意せずに2つの値を入れ替えられます。コードは短くなりますが、初心者にとっては一時変数を使った交換の方が処理の流れを理解しやすい場合もあります。学習段階ではまず一時変数で仕組みを理解し、その後で分割代入による短い書き方を覚えるとよいでしょう。
function bubbleSort(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { for (let j = 0; j < result.length - 1 - i; j++) { if (result[j] > result[j + 1]) { [result[j], result[j + 1]] = [result[j + 1], result[j]]; } } } return result;}
2.3 降順に並べる
Bubble Sortで降順に並べたい場合は、比較条件を逆にします。昇順では、左の値が右の値より大きい場合に交換しました。降順では、大きい値を前に置きたいので、左の値が右の値より小さい場合に交換します。つまり、条件式をresult[j] < result[j + 1]に変更します。比較条件を変えるだけで、同じBubble Sortの構造を使って降順ソートを実装できます。
降順ソートは、ランキングやスコア表示、売上金額の高い順、人気数の多い順などでよく使われます。Bubble Sortを使った降順実装は実務で使うためというより、比較条件によって並び順がどのように変わるのかを理解する練習として有効です。昇順と降順の違いを自分でコードに書いて確認すると、JavaScriptの標準sort()でa - bとb - aを使い分ける感覚も身につきやすくなります。
function bubbleSortDesc(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { for (let j = 0; j < result.length - 1 - i; j++) { if (result[j] < result[j + 1]) { [result[j], result[j + 1]] = [result[j + 1], result[j]]; } } } return result;}console.log(bubbleSortDesc([5, 3, 8, 1])); // [8, 5, 3, 1]
3. Bubble Sortの最適化
Bubble Sortは基本的に効率が良くないアルゴリズムですが、簡単な最適化を加えることができます。代表的なのは、1回の走査で一度も交換が発生しなかった場合に処理を終了する方法です。もし隣接要素をすべて比較しても交換が発生しなければ、その時点で配列はすでに整列されています。つまり、それ以降の走査を続けても配列の状態は変わらないため、処理を打ち切ることができます。
この最適化は、特にすでに整列済みの配列や、ほぼ整列済みの配列に対して効果があります。最悪ケースの時間計算量は変わりませんが、実際の処理回数を減らせる場面があります。アルゴリズム学習では、このような小さな最適化を考えることも重要です。単に動くコードを書くのではなく、「どこに無駄があるのか」「どの条件なら早く終了できるのか」を考えることで、より効率的なコードを書く力が身につきます。
3.1 交換フラグを使う
交換が発生したかどうかを記録するには、swappedのようなフラグ変数を使います。外側のループが始まるたびにswappedをfalseに設定し、内側のループで交換が発生したらtrueに変更します。内側のループが終わったあともswappedがfalseのままであれば、その走査では一度も交換が行われなかったことになります。その場合、配列はすでに整列済みなので、breakでループを終了できます。
この最適化により、すでに昇順に並んでいる配列に対しては、最初の1回の走査だけで処理が終わります。基本実装では不要な走査を繰り返してしまいますが、交換フラグを使うことで無駄を減らせます。Bubble Sortは大規模データ向きではありませんが、このような最適化を加えることで、アルゴリズムの改善方法を学ぶ良い例になります。
function optimizedBubbleSort(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { let swapped = false; for (let j = 0; j < result.length - 1 - i; j++) { if (result[j] > result[j + 1]) { [result[j], result[j + 1]] = [result[j + 1], result[j]]; swapped = true; } } if (!swapped) { break; } } return result;}console.log(optimizedBubbleSort([1, 2, 3, 4])); // [1, 2, 3, 4]
3.2 最適化しても限界はある
交換フラグを使うことで、整列済みやほぼ整列済みのデータでは処理回数を減らせます。しかし、Bubble Sortそのものの性質が大きく変わるわけではありません。逆順に並んだ配列やランダムな配列では、多くの比較と交換が必要になります。そのため、最悪ケースの時間計算量はO(n^2)のままです。最適化を入れたとしても、大量データを高速にソートできるアルゴリズムになるわけではありません。
この点を理解することは、アルゴリズム学習で非常に重要です。小さな改善によって実行時間を短くできる場面はありますが、アルゴリズム全体の計算量を改善するには、根本的に別のアプローチが必要になることがあります。大量データを扱う場合は、Merge SortやQuick Sortのようなより効率的なソート、またはJavaScript標準のsort()を使う方が現実的です。Bubble Sortの最適化は、あくまで学習用の改善例として捉えるとよいでしょう。
3.3 実務ではsortメソッドを使う
実務で配列を並び替える場合、Bubble Sortを自分で実装することはほとんどありません。JavaScriptには標準のArray.prototype.sort()が用意されており、通常はこちらを使います。標準メソッドはJavaScriptエンジン側で最適化されているため、一般的な用途では自作のBubble Sortよりも効率的で、コードも短く読みやすくなります。実務で重要なのは、標準メソッドを正しく使い、比較関数を適切に設計することです。
Bubble Sortを学ぶ目的は、実務でそのまま使うためではなく、ソートの基本構造を理解するためです。標準のsort()を使うと1行で終わる処理でも、内部では要素同士の比較によって並び順が決まっています。Bubble Sortを自分で実装してみることで、比較関数の意味や、データ量が増えたときの処理負荷をより具体的に理解できます。学習ではBubble Sortを使い、実務では標準メソッドを使うという切り分けが現実的です。
const numbers = [5, 3, 8, 1];const sorted = [...numbers].sort((a, b) => a - b);console.log(sorted); // [1, 3, 5, 8]
4. Bubble Sortの計算量
Bubble Sortの計算量は、アルゴリズムの効率を理解するうえで重要なポイントです。基本実装では、外側のループと内側のループを使って配列を何度も走査します。そのため、平均ケースや最悪ケースでは時間計算量がO(n^2)になります。これは、要素数が増えると処理回数が二次関数的に増えることを意味します。小さな配列では問題にならなくても、要素数が多くなると処理が重くなりやすいです。
ただし、交換フラグを使った最適化版では、すでに整列済みの配列に対しては効率よく終了できます。この場合、最初の走査で交換が一度も発生しないため、早期終了でき、時間計算量はO(n)に近くなります。とはいえ、これは最良ケースの話であり、ランダムな配列や逆順の配列では多くの比較と交換が必要です。Bubble Sortを学ぶときは、最良ケース、平均ケース、最悪ケースを分けて考えることが大切です。
4.1 最良ケース
Bubble Sortの最良ケースは、配列がすでに整列されている場合です。たとえば、昇順に並べたい配列が最初から[1, 2, 3, 4]のように並んでいれば、交換は一度も発生しません。交換フラグを使った最適化版であれば、最初の走査でswappedがfalseのままになるため、その時点で処理を終了できます。この場合、配列を1回確認するだけで済むため、時間計算量はO(n)になります。
ただし、基本実装のBubble Sortでは、配列がすでに整列されていても、決められた回数のループを実行してしまいます。そのため、最良ケースでも効率が良くない実装になる可能性があります。Bubble Sortを学ぶときは、基本実装と最適化版の違いを比較すると、早期終了の効果が分かりやすくなります。すでに整列済みのデータに対して無駄な処理をしないという考え方は、ほかのアルゴリズムや実務コードにも応用できます。
4.2 平均ケース
平均ケースは、配列の要素がランダムに並んでいる場合です。この場合、隣接要素の比較を何度も行い、必要に応じて交換する必要があります。すべての値がすぐに正しい位置へ移動するわけではないため、複数回の走査が必要になります。その結果、比較回数と交換回数が多くなり、時間計算量はO(n^2)になります。要素数が増えると、処理時間の増加が目立ちやすくなります。
平均ケースのBubble Sortは、大きな配列には向いていません。たとえば、数十件程度の小さな配列であれば学習用として問題ありませんが、数千件、数万件のデータをBubble Sortで処理すると、実行時間が長くなる可能性があります。実務でランダムな大量データを扱う場合は、JavaScript標準のsort()や、より効率的なアルゴリズムを使うべきです。平均ケースを理解することで、Bubble Sortがなぜ学習用として扱われるのかが分かります。
4.3 最悪ケース
Bubble Sortの最悪ケースは、昇順に並べたい配列が完全に逆順になっている場合です。たとえば、[5, 4, 3, 2, 1]のような配列を昇順にするには、多くの値を何度も交換する必要があります。大きな値を後ろへ移動させるだけでなく、小さな値を前へ移動させるまでに複数回の走査が必要になります。そのため、比較回数と交換回数が非常に多くなります。
最悪ケースでも、時間計算量はO(n^2)です。この性質により、Bubble Sortはデータ量が多い場合には実用的ではありません。最適化版を使っても、逆順の配列では毎回交換が発生するため、早期終了の効果はほとんどありません。Bubble Sortを理解すると、アルゴリズムの計算量がなぜ重要なのかを実感しやすくなります。単に動くコードを書くのではなく、どのような入力で処理が重くなるのかを考えることが、アルゴリズム学習の大切なポイントです。
5. Bubble Sortを学ぶときのポイント
Bubble Sortを学ぶときは、コードを暗記するのではなく、各ステップで配列がどのように変化するのかを確認することが大切です。隣接要素を比較し、必要なら交換するという動きは単純ですが、二重ループの中でどの値がどのタイミングで移動するのかを理解していないと、コードだけを見ても意味が分かりにくくなります。小さな配列を使って、1回目の走査、2回目の走査という形で状態を追うと理解しやすいです。
また、Bubble Sortを学ぶときは、なぜ内側のループ範囲を短くできるのか、なぜ交換が発生しなければ処理を終了できるのかも考えましょう。これらを理解すると、単なる実装から一歩進んで、アルゴリズムの無駄を見つける力が身につきます。Bubble Sortは効率の良いアルゴリズムではありませんが、改善点が分かりやすいため、アルゴリズムを分析する練習に向いています。
5.1 小さな配列で試す
最初は、[3, 2, 1]や[5, 1, 4]のような小さな配列でBubble Sortを試すのがおすすめです。要素数が少ない配列であれば、比較される値、交換される値、走査後の配列の状態を簡単に追うことができます。いきなり大きな配列を使うと、処理の流れが分かりにくくなるため、まずは短い配列で基本動作を確認しましょう。
小さな配列で試すと、1回の走査で最大値が後ろへ移動していく様子が見えやすくなります。また、すでに正しい位置にある要素は交換されないことも確認できます。手で処理を追ったあとにJavaScriptコードを実行すると、コードとアルゴリズムの動きがつながりやすくなります。アルゴリズム学習では、最初から複雑なケースを扱うより、シンプルな例で確実に理解することが大切です。
5.2 console.logで途中経過を見る
JavaScriptでBubble Sortを学ぶときは、ループの中にconsole.log(result)を入れて途中経過を見ると理解が深まります。交換が発生するたびに配列を出力すれば、どの値がどのように移動しているのかを確認できます。特に初心者にとって、コードだけを読んで配列の変化を想像するのは難しいことがあります。実際に出力を見ながら学ぶことで、アルゴリズムの動きがより具体的になります。
ただし、実務コードではループ内に大量のconsole.logを残すとパフォーマンスや可読性に影響するため、学習用として使ったあとは削除するようにしましょう。途中経過を確認する目的でログを使うことは非常に有効ですが、完成した関数では不要な出力を残さないことが大切です。学習段階ではログを活用し、理解できたらコードを整理するという流れで進めるとよいでしょう。
5.3 他のソートと比較する
Bubble Sortを理解したら、Selection SortやInsertion Sortと比較してみましょう。どれも基本的なソートアルゴリズムであり、平均・最悪ケースではO(n^2)になることが多いですが、処理の考え方は異なります。Bubble Sortは隣接要素を交換し、Selection Sortは未ソート領域から最小値を選び、Insertion Sortはソート済み領域へ要素を挿入します。同じソートでも、値の動き方や比較の仕方が違うことが分かります。
複数のソートアルゴリズムを比較すると、それぞれの得意なケースや苦手なケースが見えてきます。Bubble Sortは理解しやすい反面、交換回数が多くなりがちです。Selection Sortは交換回数が少ない一方で、比較回数は多くなります。Insertion Sortは、ほぼ整列済みのデータに強い特徴があります。このように比較しながら学ぶことで、アルゴリズムを単独で暗記するのではなく、目的やデータの状態に応じて考える力が身につきます。
おわりに
Bubble Sortは、隣り合う要素を比較して交換するシンプルなソートアルゴリズムです。JavaScriptで実装しやすく、比較、交換、二重ループ、早期終了といった基本的な考え方を学ぶのに適しています。アルゴリズム学習の最初の段階では、配列がどのように変化するのかを理解する教材として非常に役立ちます。
一方で、Bubble Sortは平均・最悪ケースの時間計算量がO(n^2)であり、大規模データには向いていません。実務では標準のArray.prototype.sort()を使うことが多く、Bubble Sortは主に学習目的で扱われます。Bubble Sortを理解すると、Selection SortやInsertion Sortなど他の基本ソートへ進みやすくなり、さらにMerge SortやQuick Sortのような効率的なアルゴリズムを学ぶ土台にもなります。
