【JavaScriptでアルゴリズム】並び替え（バブルソート）

今回はバブルソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。

バブルソートとは
実装
解説

バブルソートとは

まずソートとはデータを並べ替えることをいい、バブルソートとは、（昇順の場合）隣のデータと順々に比較し、大きい方を右に並べ替えるという方法のソートになります。

たとえば、
４，２，５，１，３
とランダムに並んだデータを
１，２，３，４，５
のように昇順に並べ替える場合、

４，２，５，１，３
↓
２，４，５，１，３
↓
２，４，５，１，３
↓
２，４，１，５，３
↓
２，４，１，３，５

これで最大値が一番右に移動したので、ソート済みにし、残りに対して同じ処理を繰り返します。

２，４，１，３　　５
↓
２，４，１，３
↓
２，１，４，３
↓
２，１，３，４

２，１，３　　４，５
↓
１，２，３
↓
１，２，３

１，２　　３，４，５
↓
１，２，３，４，５

実装

let nums = [4,2,5,1,3];//これをバブルソートする

for (let i = nums.length; i > 1 ; i--) {
  for (let j = 0; j < i; j++) {
    if (nums[j] > nums[j+1]) {
      let temp = nums[j];
      nums[j] = nums[j+1];
      nums[j+1] = temp;
    }   
  }
}
console.log(nums);//[1,2,3,4,5]と表示

解説

最初の for 文は、最大値をひとつずつ調べるためのものです。

for (let i = nums.length; i > 1 ; i--) {
...
}

次の for 文と if 文でデータをひとつずつ比較していき、配列の最後に最大値が移動します。

  for (let j = 0; j < i; j++) {
    if (nums[j] > nums[j+1]) {
      let temp = nums[j];
      nums[j] = nums[j+1];
      nums[j+1] = temp;
    }   
  }

そして最初の for 文にもどり、同じ処理を繰り返してソートを行います。

これでもバブルソートは実装できますが、もう少し処理が速くなるよう書き換えることができます。

たとえば極端な例ですが、１，２，３，４，５，６，７，９，８を並び替えるとします。

８と９を入れ替えるだけですべて昇順に並ぶので、その時点で処理を終えてもいいのですが、プログラムは隣同士の比較を最後まで続けてしまいます。

途中ですべて昇順に並んだらプログラムを終了するよう実装するには、以下のように書き加えます。

let nums = [1,2,3,4,5,6,7,9,8];//これを選択ソートする

for (let i = nums.length; i > 1 ; i--) {
  let notChanged = true;

  for (let j = 0; j < i; j++) {
    if (nums[j] > nums[j+1]) {
      let temp = nums[j];
      nums[j] = nums[j+1];
      nums[j+1] = temp;
      notChanged = false;
    }   
  }
  if (notChanged) {
    break;
  }
}
console.log(nums);//[1,2,3,4,5,6,7,8,9]と表示

notChanged 変数は、順番の変更があったかどうかを管理します。