バブルソートのお勉強

Algorithm C

アルゴリズムの勉強というと、まずはソートに関するアルゴリズムから始めるのがお約束ということになりましょうか。 また、ソートに関するアルゴリズムの勉強というと、だいたいバブルソートから始めることになりましょうか。

ということで、わたしもバブルソートから始めてみることにします。

二通りのサンプルコード

アルゴリズムの勉強を始めるに当たって最初に読んだ本、Java データ構造とアルゴリズム基礎講座 (長尾和彦著 技術評論社 2009 ISBN978-4-7741-3697-4) は、バブルソートを用いて昇順に並べ替える手順を次のように説明しています。 (同書 p. 160)


1. 未整列中のデータの最後の要素と隣接する直前の要素を比較し、昇順でないならデータを交換する。

2. この隣接する要素の比較と交換を、未整列データの先頭までさかのぼって繰り返す。

3. これをすべての要素を並べ替えられるまで繰り返す。

1 ラウンド目では、1 番小さなデータがうしろのほうから徐々に前に繰り上がってきて、1 番目の要素に格納されることになります。 2 ラウンド目では、2 番目に小さなデータが徐々に前に繰り上がってきて、2 番目の要素に格納されることになります。 その様子が、泡がぶくぶく言いながら上がってくるように見えるので、バブルソートと名づけられているそうです。

同書には、Java で書かれたサンプルコードが掲載されています。 それをわたしなりに C で書いてみますと、だいたい次のようになりましょうか。

void sort1(int data[], int length) {
  int i, j, tmp;
  for (i = 0; i < length - 1; i++)
    for (j = length - 1; i < j; --j)
      if (data[j - 1] > data[j]) {
        tmp = data[j - 1];
        data[j - 1] = data[j];
        data[j] = tmp;
      }
}

このコードでは、要素の数を n とすると、if 文による比較の回数は (n2-n)/2 となります。 また、2 つの要素の間でデータを交換する回数は、最小で 0、最大で (n2-n)/2 です。

つづいて、最近読んでいる本、プログラミングの宝箱 アルゴリズムとデータ構造 第2版 (紀平拓男・春日伸弥著 ソフトバンククリエイティブ 2011 ISBN978-4-7973-6328-9) をひもといてみますと、バブルソートのサンプルコードは前掲のものとは少し異なっていました。 2 つの for ループを入れ子にするのではなく、代わりにフラグを用意し、do 〜 while ループの中に for ループを置いています。 そのまま無断で掲載するのは失礼かと思いますので、わたしなりに書き直してみますと、次のようになりましょうか。

void sort2(int data[], int length) {
  int i, j, tmp, flag;
  j = 0;
  do {
    flag = 0;
    for (i = 0; i < length - 1 - j; i++)
      if (data[i] > data[i + 1]) {
        flag = 1;
        tmp = data[i];
        data[i] = data[i + 1];
        data[i + 1] = tmp;
      }
    j++;
  } while (flag == 1);
}

このコードでは、前のコードとは異なり、早い段階で全体がソート済みとなれば、その分だけ if 文による比較の回数は (n2-n)/2 よりも小さく済みそうです。 そこが flag という変数を導入したメリットにはなるでしょう。 前のコードの場合、if 文による比較の回数は常に (n2-n)/2 でしたので。

ただ、やや変数が増えてちょっとだけ読みづらいかもしれない気がします。 あるいは、それはいいとしても、while 文による条件判定が新たに付け加わっていることを考えたら、もしかしたら、思ったほど劇的に高速になるともいえない可能性もあるんじゃないかという気もします。

わたしが思い浮かべたソートアルゴリズム

ところで、バブルソートのことを知る前のわたしは、ソートアルゴリズムといえば、次のようなものを思い浮かべていました。

void sort3(int data[], int length) {
  int i, j, tmp;
  for (i = 0; i < length - 1; i++)
    for (j = i + 1; j < length; j++)
      if (data[i] > data[j]) {
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
      }
}

これは何をしているかというと、まず 1 番目の要素を 2 〜 n 番目の要素と順々に比較していき、昇順でなければそのつど入れ替えるということをおこないます。 で、1 番目の要素に 1 番小さなデータが格納されたら、次は 2 番目の要素を 3 〜 n 番目の要素と順々に比較していく、という感じです。

これは、最初に掲げた長尾さんの本によれば、「単純選択ソート (straight selection sort)」 と呼ぶものなのだそうです。 それに対して、バブルソートのほうは、「単純交換ソート (straight exchange sort)」 と呼ぶそうです。 どう呼ぶかはともかくとして、どうなのでしょう、まったくのド素人がはじめて自力でソートのアルゴリズムを考えるとしたら、どちらかというとバブルソートよりは単純選択ソートのほうを思いつくのが自然なんじゃないか、という気がしています。 わたし自身は、少なくともそうでした。 言い換えると、わたし自身は、比較的最近になってバブルソートのことを知り、効率的か非効率的かはともかくとしても、「これは思いつかなかったなあ」 という感想を持ったのは事実です。

処理速度を比較してみます

次のようなコードで、処理速度の比較をしてみました。 ちなみに、sort1 が長尾さんの実装例、sort2 が紀平さん・春日さんの実装例、sort3 が単純選択ソートの実装例、です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10000

void sort1(int data[], int length);

void sort2(int data[], int length);

void sort3(int data[], int length);

int main(void) {
  srand(time(NULL));
  int i, j, data1[N], data2[N], data3[N];
  clock_t t0, t1;
  for (i = 0; i < 10; i++) {
    for (j = 0; j < N; j++) {
      data1[j] = rand();
      data2[j] = data1[j];
      data3[j] = data2[j];
    }
    t0 = clock();
    sort1(data1, N);
    t1 = clock();
    printf("sort1 = %u, ", t1 - t0);
    t0 = clock();
    sort2(data2, N);
    t1 = clock();
    printf("sort2 = %u, ", t1 - t0);
    t0 = clock();
    sort3(data3, N);
    t1 = clock();
    printf("sort3 = %u\n", t1 - t0);
  }
}

これの結果は、わたしの手元の環境では、たとえば次のようになりました。

sort1 = 484, sort2 = 497, sort3 = 478
sort1 = 483, sort2 = 484, sort3 = 464
sort1 = 474, sort2 = 479, sort3 = 468
sort1 = 468, sort2 = 489, sort3 = 473
sort1 = 479, sort2 = 483, sort3 = 478
sort1 = 460, sort2 = 511, sort3 = 506
sort1 = 481, sort2 = 501, sort3 = 485
sort1 = 488, sort2 = 491, sort3 = 475
sort1 = 476, sort2 = 476, sort3 = 478
sort1 = 483, sort2 = 487, sort3 = 484

どれもほとんど大差ないようです。 ほんのわずかに、sort2 だけは数ミリ秒単位で時間がかかる傾向があるように感じます。 前述した、while 文による条件判定が新たに付け加わった点が、若干影響したのかもしれません。

ただ、sort2 が劇的に高速に処理するケースは、たしかにあります。 それは、与えられた配列が、すでにソート済みの場合です。 ソート済みの場合、sort2 は、ほとんどすることがないので、もう 0 ミリ秒に近いくらいに高速です。 たとえば、main 関数の中で data1[j] = rand(); という部分を data1[j] = j; と書き直して、つまり最初からソート済みの配列を与えた場合、結果は次のようになりました。

sort1 = 209, sort2 = 0, sort3 = 212
sort1 = 207, sort2 = 0, sort3 = 212
sort1 = 212, sort2 = 0, sort3 = 215
sort1 = 209, sort2 = 0, sort3 = 205
sort1 = 206, sort2 = 0, sort3 = 206
sort1 = 197, sort2 = 0, sort3 = 203
sort1 = 202, sort2 = 0, sort3 = 215
sort1 = 206, sort2 = 0, sort3 = 204
sort1 = 208, sort2 = 0, sort3 = 207
sort1 = 206, sort2 = 0, sort3 = 207

あるいは、そこまで完璧にソート済みでなくとも、前のほうの要素から後のほうの要素にかけて、だいたいの傾向として昇順でソートされつつあるようなの状態であれば、やはり sort2 は高速のようです。

結論

長尾さんのバブルソートの実装例は、単純選択ソートの実装例と、ほぼ同程度の処理速度と言えそうです。 たしかに、比較の回数はどちらも (n2-n)/2 で一定しています。 それに対して、紀平さん・春日さんのバブルソートの実装例は、与えられた配列の要素がランダムに並んでいる場合には特に何もない (もしかしたら数パーセントほど遅い) ですが、配列の要素が多少なりとも昇順の傾向のある状態にある場合には、けっこう威力を発揮するように見受けられます。

今後、他のもっと高速なソートアルゴリズムを利用しながら、最後の詰めはバブルソートでおこなうっていうようなケースでは、紀平さん・春日さんの実装例は参考になるかもしれない、と思いました。

以上、おしまい。