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

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

TechAcademyマガジンは受講者数No.1のオンラインプログラミングスクールTechAcademy [テックアカデミー]が運営。初心者向けに解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。

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

JavaScriptについてそもそもよく分からないという方は、JavaScriptとは何なのか解説した記事をまずご覧ください。

 

なお本記事は、TechAcademyのオンラインブートキャンプ、JavaScript/jQuery講座の内容をもとにしています。

 

田島悠介

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

大石ゆかり

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

田島悠介

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

大石ゆかり

お願いします!

 

目次

  1. バブルソートとは
  2. バブルソートを実装する方法
  3. 実際に書いてみよう
  4. まとめ

 

バブルソートとは

並べ替えをする方法の一つです。隣同士の大小を比べて入れ替えることを繰り返して、小さい順や大きい順に並べ替えます。

数を小さい順に並べる場合、下から比較して一つづつ入れ替えることを繰り返すと、小さい数が上に移動していくことになります。その様子が泡が浮かんでいく様子に似ているのでバブルソートという名前になっています。

[PR] JavaScript・jQueryで挫折しない学習方法を動画で公開中

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

数字を小さい順に並べる例をつかって、実装方法を説明します。数字を縦に並べて、一番上または一番下の数と隣の数を比較していきます。

数が小さければ交換し、小さくなければそのままにし、それを最後まで繰り返します。すると、一番小さい数が一番上に上がってきます。この動作を繰り返すのですが、文字だけだとイメージしにくいので具体的に数を並び替えて説明します。

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

1周目

まずは、一番下の数「1」と、その隣の数「5」を比較し、「1」の方が小さいので場所を交換します。
次に、下から2番目の数「1」と、その隣の数「10」を比較し、「1」の方が小さいので場所を交換します。
下から3番目の数「1」と、その隣の数「3」を比較し、「1」の方が小さいので場所を交換します。
下から4番目の数「1」と、その隣の数「7」を比較し、「1」の方が小さいので場所を交換します。
一番下から上まで比較をしているので、スポーツのトーナメント表などで勝ち上がって優勝したのと同じことになります。つまり、この時点で一番上にある「1」は、一番小さいことが確定します。

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

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

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

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

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

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

これで、上から4番目の「7」が確定し、同時に残り1つなので一番下の「10」も確定しました。
小さい順に並べ終わり、バブルソート終了です。

実際に書いてみよう

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

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

for(let outer = 0; outer < array.length -1; outer++){
  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箇所か書き換えることで、小さい順から大きい順に変わります。よければその場所を探してみてください。

筆者プロフィール

横山茂雄(よこやましげお)

フリーエンジニアとして活動中。サーバーサイドからフロントまで時代の波に合わせてスキルを変化させてきました。

言語、フレームワーク、DB、現場、いずれも転々としながら、筋トレも欠かさない体育会系エンジニアです。TechAcademyジュニアのゲームアプリコースを担当しています。

 

大石ゆかり

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

田島悠介

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

大石ゆかり

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

 

TechAcademyでは、初心者でも最短4週間で、JavaScript・jQueryを使ったWebサービス公開を習得できる、オンラインブートキャンプを開催しています。

また、現役エンジニアから学べる無料体験も実施しているので、ぜひ参加してみてください。