バブルソート(単純交換ソート)

2013年3月23日：アルゴリズム

ソートにおいて簡単に組めるアルゴリズムにバブルソート(単純交換ソート)があります。

バブルソートは、簡単に組めるというメリットがあります。

一方、実行速度はそれほど速くないというデメリットもあります。

速度を意識しなくていい場合は、バブルソートでいいでしょう。

バブルソートのアルゴリズム

実際に、アルゴリズムを実行してバブルソートを体感します。

いま

1,4,2,8,1,3

という数列があるとします。これをバブルソートで小さい順に並べ替えます。

バブルソートは、右から左へ小さい数が上がっていく(移動する)様子から名付けられました。

具体的には

  • 1,4,2,8,1,3  (1と3を比較して低い数を左へ)
  • 1,4,2,8,1,3  (8と1を比較して低い数を左へ)
  • 1,4,2,1,8,3  (2と1を比較して低い数を左へ)
  • 1,4,1,2,8,3  (4と1を比較して低い数を左へ)
  • 1,1,4,2,8,3  (1と1を比較して低い数を左へ)

とします。こうすれば、もっとも低い数が左にきます。

1,1,4,2,8,3

一番左は確定なので、次に青色の1,4,2,8,3 で同様の操作をします。

  • 1,4,2,8,3
  • 1,4,2,3,8
  • 1,4,2,3,8
  • 1,2,4,3,8

これで、1,1,2,4,3,8のうち赤色の部分が完了して、青色の部分を再び実行します。

これをすべてが完了するまでやるのがバブルソートです。

バブルソートのコーディング

バブルソートをコーディングすると以下のようになります。

小さい順へソート

void bubble_sort(int a[], int n){
    int i,j;
    for(i=0;i<n-1;i++){          //最初からn-2まで順に確定する
        for(j=n-1;j>i;j--){      //最後からi+1まで順に小さいのを押し出す
            if(a[j-1]>a[j]){     //もし後ろの要素a[j]が小さいなら交換
                int temp=a[j-1]; //一時保存
                a[j-1]=a[j];     //a[j-1]とa[j]を交換
                a[j]=temp;
            }
        }
    }
}

大きい順へソート

void bubble_sort(int a[], int n){
    int i,j;
    for(i=0;i<n-1;i++){          //最初からn-2まで順に確定する
        for(j=n-1;j>i;j--){      //最後からi+1まで順に大きいのを押し出す
            if(a[j-1]<a[j]){     //もし後ろの要素a[j]が大きいなら交換
                int temp=a[j-1]; //一時保存
                a[j-1]=a[j];     //a[j-1]とa[j]を交換
                a[j]=temp;
            }
        }
    }
}

計算量の見積もり

要素数がnとして、計算量を見積もってみましょう。

ループが２つあり、

  • 1回目：n-1
  • 2回目：n-2
  • 3回目：n-3
  • …
  • n-1回目：1

なので、

(n-1)+(n-2)+…+1=n(n-1)/2

となります。

著者：安井 真人(やすい　まさと)

TOP