バブルソート(単純交換ソート)
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として、計算量を見積もってみましょう。
ループが2つあり、
- 1回目:n-1
- 2回目:n-2
- 3回目:n-3
- …
- n-1回目:1
なので、
(n-1)+(n-2)+…+1=n(n-1)/2
となります。
著者:安井 真人(やすい まさと)
@yasui_masatoさんをフォロー