バブルソートの改良

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;    //おわり
        }
    }
}

ちょっとだけ変更した配列のソートに使ってみてください。

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

TOP