icon
icon

JavaScriptでバブルソートを実装する方法を現役エンジニアが解説【初心者向け】

初心者向けにJavaScriptでバブルソートを実装する方法について現役エンジニアが解説しています。バブルソートとは並べ替えをする方法の一つで、隣同士の大小を比べて入れ替えることを繰り返して並べ替えます。バブルソートのサンプルとして配列の値をソートする方法を解説します。

テックアカデミーマガジンは受講者数No.1のプログラミングスクール「テックアカデミー」が運営。初心者向けにプロが解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。 ※ アンケートモニター提供元:GMOリサーチ株式会社 調査期間:2021年8月12日~8月16日  調査対象:2020年8月以降にプログラミングスクールを受講した18~80歳の男女1,000名  調査手法:インターネット調査

監修してくれたメンター

永井浩平

BtoBtoC事業を行っている会社で社内SEとして勤務。
バックエンド、フロント、クラウドなど幅広く業務を行う。
テックアカデミーでは、フロントエンドコース / Javaコースのメンター。

JavaScriptでバブルソートを実装する方法について、テックアカデミーのメンター(現役エンジニア)が実際のコードを使用して初心者向けに解説します。

目次

そもそもJavaScriptについてよく分からないという方は、JavaScriptとは何なのかについて解説した記事を読むとさらに理解が深まります。

 

田島悠介

今回は、JavaScriptに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

JavaScriptでバブルソートを実装する方法について詳しく説明していくね!

大石ゆかり

お願いします!

 

はじめに

一覧などの並び替え(昇順・降順)で使われているソート方法について、その仕組みとJavaScriptで実装する方法について紹介します。

普段は「配列オブジェクト.sort()」とすることで、以下のように配列などの要素を並び替えることができます。

 

ソートのやり方は「バブルソート」、「クイックソート」、「マージソート」などさまざまな方法がありますが、今回は「バブルソート」について説明します。

まずはバブルソートの仕組みについて覚えていきましょう。

 

バブルソートとは

並べ替え(ソート)をする方法の代表的な1つです。

他のソートと同じく、隣同士の大小を比較する点は変わりません。

しかし、比較する順番や比較結果により、要素の入れ替え方法が異なります。

バブルソートでは、要素の端(先頭または末尾)から比較し、比較結果により要素を1つずつ入れ替えて、再び比較を行っていきます。

例えば、数を小さい順に並べる場合、下から比較して1つずつ入れ替えることを繰り返すと、小さい数が上に移動していきます。

一番上まで要素が移動した場合、その要素は比較対象の中で最も小さい要素です。

その様子が、泡が浮かんでいく様子に似ているのでバブルソートという名前になっています。

 

[PR] コーディングで副業する方法とは

バブルソートを実装する方法

数字を小さい順に並べるソートを例に、実装方法を説明します。

数字を縦に並べて、一番上または一番下の数と隣の数を比較していきます。

数が小さければ交換し、小さくなければそのままにし、それを最後まで繰り返します。
最終的に、一番小さい数が一番上に上がってきます。

1要素に対して一連の比較が終わったら、また末尾の要素に移動しこの動作を繰り返し、要素を昇順(小さい順)に並べていきます。

文字だけだとイメージしにくいので、具体的に数を並び替えて説明します。

「7, 3, 10, 5, 1」と5つの数字が格納された配列を用意して、バブルソートで並び替えます。

 

1周目

一番下の数「1」とその上の数「5」を比較します。
「1」の方が小さいので場所を交換します。
次に、下から2番目の数「1」とその上の数「10」を比較します。
「1」の方が小さいので場所を交換します。
下から3番目の数「1」とその上の数「3」を比較します。
「1」の方が小さいので場所を交換します。
下から4番目の数「1」とその隣の数「7」を比較します。
「1」の方が小さいので場所を交換します。
一番下から上まで総当たりで比較しました。
この時点で一番上にある「1」は、一番小さいことが確定します。

一番上の数が確定しているので、一番上を除いてもう一度同じように下から比較していきます。

ここでポイントとなるのが、1番目の要素は最小であることが確定している点です。

2周目以降から、比較する回数が前の周に比べて少なくなっていきます。

 

2周目
一番上を除く以外は1周目と同じなので、比較と交換の流れのみ表記します。

これで上から2番目の「3」が確定しました。

3週目は3~5の要素のみ比較をしていきます。

 

3周目
確定している一番上と2番目の数を除いて、一番下から比較していきます。

これで上から3番目の「5」が確定しました。

 

4周目
確定している一番上から3番目の数を除いて、一番下から比較していきます。

これで、上から4番目の「7」が確定し、同時に残り1つなので一番下の「10」も確定しました。

小さい順に並べ終わり、バブルソート終了です。

 

実際に書いてみよう

上で紹介した「7, 3, 10, 5, 1」を使った動きをJavaScriptにしてみます。

1つ目のfor文のouterが何周目かを表しています。

2つ目のfor文のiが比較対象の要素を表しています。

1周目、2周目と進んでいく度に、array[i]の比較対象の要素数は減っていきます。

//ソート前の配列データ
let array = [7, 3,10, 5, 1];

for(let outer = 0; outer < array.length -1; outer++){
    console.log(outer + 1 + "周目");
    for(let i = array.length-1; i > outer; i--){    
        if(array[i] < array[i-1]){
            let tmp = array[i];
            array[i] = array[i-1];
            array[i-1] = tmp;
        }
    }
}
console.log(array); // [1, 3, 5, 7, 10]

解説

2重のループになっています。

1つ目(外側)のforループでは、確定したものを除外するために比較する要素の終わりの数を、outerという名前の変数にして1つずつ増やしています。

これにより、1周目は一番最後の要素から一番最初の要素0までとなり、2周目は、一番最初の要素0を除いた要素1までという動きになります。

2つ目(内側)のforループでは、配列の一番最後から数を減らすことで最初の要素に向かって比較をしています。

要素の値を入れ替える際は、一時保存用の変数(ここではtmp)に隣の要素の値を格納してから、交換する値を上書きし、その後で一時保存用の変数に格納した値を交換元の要素に格納して実現しています。

 

まとめ

基本的な並び替えの処理は標準で用意されているので、中でどのように動いているかを意識することは少ないと思います。

しかし、独自のオブジェクトやデータのかたまりを並び替える必要ができた際に、このような仕組みを知っていると対応がスムーズにできます。

今回紹介したソースも1箇所を書き換えることで、小さい順から大きい順に変えることができます。

ぜひ大きい順に変更する方法を探してみてくださいね。

大石ゆかり

内容が分かりやすくて良かったです!

田島悠介

ゆかりちゃんも分からないことがあったら質問してね!

大石ゆかり

分かりました。ありがとうございます!

 

JavaScriptを学習中の方へ

これで解説は終了です、お疲れさまでした。

  • つまずかず「効率的に」学びたい
  • 副業や転職後の「現場で使える」知識やスキルを身につけたい

プログラミングを学習していて、このように思ったことはありませんか?

テックアカデミーのフロントエンドコースでは、第一線で活躍する「プロのエンジニア」が教えているので、効率的に実践的なスキルを完全オンラインでしっかり習得できます。

合格率10%の選考を通過した、選ばれたエンジニアの手厚いサポートを受けながら、JavaScript・jQueryを使ったWebサービス開発を学べます。

まずは一度、無料体験で学習の悩みや今後のキャリアについて話してみて、「現役エンジニアから教わること」を実感してみてください。

時間がない方、深く知ってから体験してみたい方は、今スグ見られる説明動画から先に視聴することをおすすめします!