bablemd-compressor
バブルソートは、配列の隣同士の要素を比較しながら並べ替えるアルゴリズムです。

最大値または最小値が泡のように浮き上がってくるような挙動からバブル（bubble：泡）ソートと呼ばれます。


１ 》バブルソート図解

（昇順に並び替える）
  1. 配列の最右端h[j]の要素とその隣h[j-1]の要素を比較
  2. h[j-1]の要素がh[j]の要素より大きければ交換
  3. jを-1しながら未ソート部の先頭との比較になるまで繰り返す
  4. この手順から未ソート部の左端に最小値が確定する
  5. 以上の操作を(h.length - 1)回繰り返すと完了
※配列の最左端h[i]とその隣の要素h[i+1]の要素を比較し、未ソート部の右端に最大値を確定させる方法でも可。

具体例を次に示す
bable1-compressor
  1. 未ソート部右端h[j]とその隣の要素h[j-1]を比較
  2. h[j]の要素よりh[j-1]の要素が大きいとき要素を交換
  3. jを-1する
  4. 1，2，3の操作を未ソート部最左端との比較になるまで繰り返す
  5. このとき未ソート部左端に最小値が確定
  6. 未ソート部最左端の位置を右へ1つ更新
  7. 2，3，4，6の操作を（h.length-1）回繰り返す
上の例では4回繰り返す

ソート完了

特徴


  • 同一キーを持つ要素の順序がソート前後で維持される
　　→安定なソート


計算量


データ数をNとすると

合計比較演算回数　N(N - 1)/2

バブルソートのオーダー　O(N^2)


２ 》バブルソートプログラム


配列の中身を昇順に並び替える

【JavaScript】
//バブルソートを行う関数
function bubbleSort(hairetu)
{
    //値を交換するための変数
    var temp;

    for(var i=0;i < (hairetu.length-1);i++) 
    {
        for(var j=(hairetu.length-1);j > i;j--)
        {
            if(hairetu[j-1] > hairetu[j]) 
            {
                temp = hairetu[j-1];
                hairetu[j-1] = hairetu[j];
                hairetu[j] = temp;
            }
        }
    }
}              

//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前：");
for(var i=0; i < h.length;i++)
{
    document.write(h[i]+" ");
}
document.write("<br>");

//バブルソート
bubbleSort(h); 

document.write("整列後：");
for(var i=0; i < h.length; i++)
{
    document.write(h[i]+" ");
}

【実行結果】
整列前：6 3 8 4 5 1 2 9 7 0
整列後：0 1 2 3 4 5 6 7 8 9


３ 》その他ソート

  1. 選択ソート
  2. バブルソート
  3. 挿入ソート
  4. マージソート
  5. シェルソート
  6. ヒープソート
  7. クイックソート