javascriptでバブルソートを実装

スポンサーリンク
Pocket
LINEで送る

今回はjavascriptでバブルソートを実装していきます。

バブルソートはソートアルゴリズムの一つで、「上から順に隣り合った値を見て大きかったら入れ替える」これを繰り返しソートをかけていくというシンプルなアルゴリズムです。

 

[0, 30, 23, 45, 111, 2, 44]

こういった配列の場合、まず、44と2の二つを比べます。

44は2より小さいのでこれはスルー。

次に2と111を比べます。

111の方が大きいので2と111を入れ替えます。

[0, 30, 23, 45, 2, 111, 44]

するとこうなりますね。

これを繰り返します。

 

javascriptで実装してみる

function bubble_sort(){
  var target = [32, 2, 445, 31, 14, 53, 68, 93];
 
  for(var i=0; i < target.length-1; i++){

    for(var j = target.length-1; j>i; j--){
      if(target[j] < target[j-1]){
        t = target[j];
        target[j] = target[j-1];
        target[j-1]= t;
      }
    }

  }

  return target;
}

console.log(bubble_sort());

 

バブルソーとは仕組みが簡単な分、非効率なソートです。

スポンサーリンク

 

「比較回数」は、高々n(n-1)/2回。交換回数は、元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では平均n(n-1)/4回。(O(n2))