バブルソートの改良
2013年3月24日:アルゴリズム
前にバブルソートを紹介しました。
バブルソートを使えば、数列を昇順や降順に並び替えることができます。
ここでは前に紹介したバブルソートを改良して、速く動作するようにしましょう。
ほとんど整列している場合を考える
ソートをする際、一部を変更したので再びソートをし直したい場合があると思います。
例えば、
1,2,3,4,5
の一部を変更して
1,2,9,4,5
となったのをソートしたいという場合です。
実際にバブルソートすると
- 1,2,9,4,5
- 1,2,9,4,5
- 1,2,4,9,5
- 1,2,4,9,5
これで最前列が確定です。同様にして2列目以降をやると
- 1,2,4,9,5
- 1,2,4,5,9
- 1,2,4,5,9
となります。3列目も同様に
- 1,2,4,5,9
- 1,2,4,5,9
となり、最後に
- 1,2,4,5,9
となり終了です。以上の操作から、2列目が終わったらもうやらなくてもいいことに気が付きます。
この気付きを活かすことで、バブルソートを高速化できます。
どうやって高速化するか
ではどうやって高速化するかを紹介します。それは
交換することがなくなったら終わる
です。前の例だと、3列目をソートした際に、交換する場所がありませんでした。ですから、4列目をやならいで終わればいいのです。
この操作は、ほとんど整列している場合に威力を発揮します。
一部変更して、ソートしたい場合は途中でおわるという操作が有効です。
例えば、すべてソートされている場合
1,2,3,4,5,6,7,8
は一回目で交換がないことを確認して終了します。もし、打ち切りがなければ
7+6+5+4+3+2+1=28
と28-7=21回も多く計算します。配列の数が多くなると大きな差となりますね。
バブルソート改のコーディング
具体的にコーディングすると以下のようになります。
void bubble_sort_kai(int a[],int n){ int i,j; for(i=0;i<n-1;i++){ bool noexchg=true; //交換したか判定する for(j=n-1;j>i;j--){ if(a[j-1]>a[j]){ int tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; noexchg=false; } } if(noexchg){ //もし交換がないなら break; //おわり } } }
ちょっとだけ変更した配列のソートに使ってみてください。
著者:安井 真人(やすい まさと)
@yasui_masatoさんをフォロー