単純挿入ソート

Algorithm C

昨日の日記 単純選択ソート (Nov 23, 2011) で、単純選択ソートをわたしなりに安定ソート化してみようと試みた際に、これはもしかしたら単純挿入ソートに変質してしまったのではなかろうか、という疑問を抱きました。 で、そもそも、単純挿入ソートって、どういうものだっけ、ということで、これについて勉強してみました。

長尾さんの単純挿入ソート

前回と同様、まずは Java データ構造とアルゴリズム基礎講座 (長尾和彦著 技術評論社 2009 ISBN978-4-7741-3697-4) p.165 に掲載されているサンプルコードを参照のうえ、習いたての C でわたしなりに書き直してみたいと思います。

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

内側の for ループでは、0 番目から i - 1 番目までは仮に整列済みとみなしたうえで、i 番目の要素を挿入すべき場所を、うしろから前に向かって探していくようにしています。 また、挿入すべき場所を空けるために、各要素をひとつずつうしろにずらすということも同時にしています。 最後の data[j] = tmp; という代入処理は、j が i より小さいかどうかを判定したうえででなくても構わないのですが、より一般化して考えた場合に、もしかしたら代入自体がそこそこ時間のかかる処理だというケースもありえるんじゃないかと思うので、j と i が等しい場合にはわざわざ代入処理する必要がないということを明示しようとしたものです。

紀平さん・春日さんの単純挿入ソート

つづいて、もうひとつ、今度は プログラミングの宝箱 アルゴリズムとデータ構造 第2版 (紀平拓男・春日伸弥著 ソフトバンククリエイティブ 2011 ISBN978-4-7973-6328-9) の pp.21-22 に掲載されているサンプルコードを参照してみたのですが、正直なところ、処理内容を理解するのに若干時間がかかりました。 ごく一部だけ改変したうえで、ほとんど丸写ししてしまいますと、次のようになります。

void sort7(int data[], int length) {
  int i, sorted, temp, insert;
  for (sorted = 0; sorted < length - 1; sorted++) {
    insert = data[sorted + 1];
    for (i = 0; i <= sorted; i++)
      if (data[i] > insert)
        break;
    while (i <= sorted + 1) {
      temp = data[i];
      data[i] = insert;
      insert = temp;
      i++;
    }
  }
}

sort6 と sort7 とで異なる点のひとつは、前者の場合は挿入すべき場所をうしろから前に向かってサーチするのに対して、後者の場合は前からうしろに向かってサーチする、といったところでしょうか。 そういうことであれば、わたしは、どちらかというと、次のように書いてみたい気がします。

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

変数名は、sort6 と比較しやすいように、だいぶ変えてしまいました。 また、sort7 が while ループで処理していた部分も、書き換えています。

処理速度の比較

それでは、sort6、sort7、sort8 の処理速度を、比較してみたいと思います。 なお、昨日の日記で採り上げました長尾さんの単純選択ソートも、sort4 として、比較の対象にしてみます。 (sort4 の実装コードは昨日の日記をご参照ください。)

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

#define N 10000

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

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

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

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

int main(void) {
  srand(time(NULL));
  int i, j, data4[N], data6[N], data7[N], data8[N];
  clock_t t0, t1;
  for (i = 0; i < 10; i++) {
    for (j = 0; j < N; j++) {
      data4[j] = rand();
      data6[j] = data4[j];
      data7[j] = data6[j];
      data8[j] = data7[j];
    }
    t0 = clock();
    sort4(data4, N);
    t1 = clock();
    printf("sort4 = %u, ", t1 - t0);
    t0 = clock();
    sort6(data6, N);
    t1 = clock();
    printf("sort6 = %u, ", t1 - t0);
    t0 = clock();
    sort7(data7, N);
    t1 = clock();
    printf("sort7 = %u, ", t1 - t0);
    t0 = clock();
    sort8(data8, N);
    t1 = clock();
    printf("sort8 = %u\n", t1 - t0);
  }
}

そういえば、わたしの環境について、述べていませんでした。 CPU は Intel Core2 Duo P8600 2.4GHz で、OS は Microsoft Windows 7 Professional SP1 (32-bit) です。 MinGW GCC 4.5.2 でコンパイルして実行しています。 実行結果は、次のとおりでした。

sort4 = 206, sort6 = 137, sort7 = 209, sort8 = 178
sort4 = 205, sort6 = 133, sort7 = 213, sort8 = 179
sort4 = 206, sort6 = 136, sort7 = 209, sort8 = 171
sort4 = 214, sort6 = 136, sort7 = 210, sort8 = 178
sort4 = 206, sort6 = 136, sort7 = 214, sort8 = 178
sort4 = 206, sort6 = 136, sort7 = 213, sort8 = 172
sort4 = 211, sort6 = 137, sort7 = 210, sort8 = 178
sort4 = 206, sort6 = 134, sort7 = 209, sort8 = 177
sort4 = 207, sort6 = 135, sort7 = 212, sort8 = 178
sort4 = 226, sort6 = 137, sort7 = 214, sort8 = 181

これを見ると、長尾さんの単純挿入ソート、すなわち sort6 が最も速いようです。 また、我田引水、手前味噌な強弁で恐縮ですが、紀平さん・春日さんの単純挿入ソートをわたしなりに書き直してみた sort8 も、まあまあ健闘 (?) しているといえましょうか。

ちなみに、上の結果は、与えられた配列の値がランダムに並んでいることを想定したものです。 もし、あらかじめ昇順でソート済み、または、降順でソート済みだったら、各ソートアルゴリズムの比較結果はどうなるでしょうか。 実際のところ、それぞれ、次のようになりました。

昇順でソート済みの配列を与えた場合

sort4 = 214, sort6 = 0, sort7 = 165, sort8 = 164
sort4 = 204, sort6 = 0, sort7 = 165, sort8 = 167
sort4 = 204, sort6 = 0, sort7 = 165, sort8 = 163
sort4 = 204, sort6 = 0, sort7 = 163, sort8 = 165
sort4 = 204, sort6 = 0, sort7 = 163, sort8 = 164
:

降順でソート済みの配列を与えた場合

sort4 = 216, sort6 = 274, sort7 = 257, sort8 = 193
sort4 = 208, sort6 = 278, sort7 = 259, sort8 = 192
sort4 = 214, sort6 = 274, sort7 = 257, sort8 = 195
sort4 = 215, sort6 = 271, sort7 = 257, sort8 = 192
sort4 = 215, sort6 = 271, sort7 = 253, sort8 = 197
:

こうして眺めてみると、与えられた配列の並びに何らかの傾向があると、長尾さんの単純挿入ソート (sort6) は処理速度のブレがやや大きいようです。 紀平さん・春日さんの単純挿入ソート (sort7 および sort8) も、ブレがないわけではないですが、いくらか緩和されているようです。 また、単純選択ソート (sort4) は、ほとんどブレがなく、処理速度はほぼ一定といえそうです。

全体的には、大変しつこくて申し訳ないのですが、わたしなりに書いてみた sort8 が最も穏当なところなんじゃないかという気がしています。 単純挿入ソートなら安定ソートですし、単純選択ソートに比べて若干高速という傾向があるようにも見受けられます。

まとめ

今回まで 3 回にわたって、単純交換ソート (バブルソート) と単純選択ソートと単純挿入ソートを見てきました。 前回は、単純交換ソートに比べて、単純選択ソートはずいぶん高速なんだなあと実感したところでした。 が、今回は、それよりも単純挿入ソートのほうが、さらにもう少し高速なんだなあと思いました。

参考にしたサンプルコードとしては、紀平さん・春日さんのものよりも、長尾さんのもののほうが、わたしには理解しやすく、また若干高速だったような気がします。 ただ、長尾さんの前掲書 p.165 には、単純挿入ソートに関して、次のような記述がありました。


要素の比較回数、交換回数は、ともに (n2-n)/2、計算量 (オーダ) は O(n2) となります。

これは、違うんじゃないでしょうか。 もし、そうだとしたら、単純交換ソートと変わらず、もっと処理が遅いという結果になったはずです。 実際には、仮に整列済みの部分配列の中に、挿入すべき場所を見つけられればいいので、比較回数はもっとずっと少なくて済むはずだと思います。 おそらく最悪のケースでないかぎり、(n2-n)/2 にまではならないと思います。 紀平さん・春日さんの前掲書のほうでは、その点についての言及はありませんでした。 で、Wikipedia 日本語版の 挿入ソート の記事 (May 24, 2011) を読んでみますと、たしかに、挿入ソートは比較回数がそれよりも少なくて済むから高速だ、という趣旨の説明がありました。

ともあれ、いずれにせよ、本日のところは、単純挿入ソートがちょっと気に入りました。

以上、おしまいです。