二通りの挿入ソート
これまでに、交換ソート (バブルソート)、選択ソート、挿入ソートを、大雑把に眺めてきました。 いずれも、計算量オーダーが O(N2) であるとされているアルゴリズムです。 これらの中では、個人的には挿入ソートがちょっと気に入りました。 あまり難解もしくは複雑ではありませんし、そこそこ高速に処理することができるように見受けられたからです。
挿入ソートには、前回の日記 単純挿入ソート (Nov 24, 2011) で試した 単純挿入ソート (straight insertion sort) のほかに、二分挿入ソート (binary insertion sort) というものがあるのだそうです。 挿入すべき場所を探索する際に単純挿入ソートではリニアサーチをおこない、二分挿入ソートではバイナリサーチをおこなうというのが、両者のおもな違いです。
二分挿入ソートについては、Java データ構造とアルゴリズム基礎講座 (長尾和彦著, 技術評論社, 2009 年, ISBN978-4-7741-3697-4) では触れられていません。 しかしながら、プログラミングの宝箱 アルゴリズムとデータ構造 第2版 (紀平拓男・春日伸弥著, ソフトバンククリエイティブ, 2011 年, ISBN978-4-7973-6328-9) では触れられています。 わたし自身は、この紀平さん・春日さんの本を読んで、二分挿入ソートのことを知りました。
安定ソート
同書 p.23 には、次のような記述が見られます。
ソートするデータの数が多いときには、バイナリサーチが威力を発揮してくるので、効率がずいぶんと改善されます。 アルゴリズムの性質は単純挿入ソートと同じで、計算量オーダは O(N2)、ソートの安定性は 「安定」 です。
このあと、サンプルコードが掲載されているのですが、ひとつ疑問を感じました。 これは本来あまり行儀のよいことではないのかもしれませんが、言葉でうまく説明することが苦手なものですので、あえて該当部分 (同書 pp.23-24) を丸写しして以下に引用させていただきたいと思います。
#define N 10 /* データの件数 */ int sort[N]; void BinaryInsertSort(void) { int i, sorted, temp, insert; int left, mid, right; /* バイナリサーチ用の追加変数 */ /* 最初から最後まですべてソート済みになるまで繰り返す */ for(sorted = 1; sorted < N; sorted++) { /* ソート済み領域の直後の値を取り出す */ insert = sort[sorted]; /* 挿入する場所を見つける(バイナリサーチ) */ left = 0; right = sorted; while(left < right) { mid = (left + right) / 2; if(sort[mid] < insert) { left = mid + 1; } else { right = mid; } } i = left; /* ソート済み領域直後の値を挿入する (単純挿入ソートと同じ) */ while(i <= sorted) { temp = sort[i]; sort[i] = insert; insert = temp; i++; } } }
やや引用が長くなって恐縮ですが、この中でわたしが疑問に思ったのは一箇所です。 挿入する場所を見つけるバイナリサーチの while ループの中に見られる、if(sort[mid] < insert) 〜 else という条件分岐の部分です。 この場合、もし sort[mid] の値と insert の値が等しい場合は else 以下に制御が移り、right = mid; が実行されます。 つまり、挿入すべき場所を、もっと前のほうで再び探し求めるのだ、ということになります。 これでは、安定ソートにならないと思うのです。
わたしの考えでは、たぶん、判定式を sort[mid] <= insert と書き直せば、安定ソートになるのではないかと思います。
処理速度の比較
さて、単純挿入ソートと二分挿入ソートとで、処理速度を比較してみたいと思います。
まず、単純挿入ソートの実装コードは、前回の日記の sort6 とほぼ同様ですが、次のとおりとします。
void isort0(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]; data[j] = tmp; } }
また、二分挿入ソートの実装コードは、前掲の紀平さん・春日さんのサンプルコードを参考にしつつ、変数名などなどを書き換えまして、次のとおりとします。
void isort1(int data[], int length) { int i, j, tmp; int left, middle, right; for (i = 1; i < length; i++) { tmp = data[i]; left = 0; right = i; while (left < right) { middle = (left + right) / 2; if (data[middle] <= tmp) left = middle + 1; else right = middle; } for (j = i; left < j; --j) data[j] = data[j - 1]; data[j] = tmp; } }
そして、これらの処理速度を比較するためのテストコードは、次のとおりとします。
#include <stdio.h> #include <stdlib.h> #include <time.h> void isort0(int data[], int length); void isort1(int data[], int length); #define N 10000 int main(void) { int i, j; int data0[N], data1[N]; clock_t t0, t1; srand((unsigned int)time(NULL)); for (i = 0; i < 10; i++) { for (j = 0; j < N; j++) { data0[j] = rand(); data1[j] = data0[j]; } t0 = clock(); isort0(data0, N); t1 = clock(); printf("isort0 = %d, ", t1 - t0); t0 = clock(); isort1(data1, N); t1 = clock(); printf("isort1 = %d\n", t1 - t0); } return EXIT_SUCCESS; }
さて、わたしの手元の環境でコンパイルして実行してみますと、次のような結果を得ました。
isort0 = 137, isort1 = 98 isort0 = 139, isort1 = 99 isort0 = 136, isort1 = 99 isort0 = 140, isort1 = 100 isort0 = 138, isort1 = 98 isort0 = 137, isort1 = 100 isort0 = 139, isort1 = 101 isort0 = 138, isort1 = 90 isort0 = 141, isort1 = 93 isort0 = 141, isort1 = 93
ちなみに、最初から昇順でソート済みの配列を与えた場合の処理時間は、どちらのアルゴリズムもほぼ 0 ミリ秒でした。 また、降順でソート済みの配列を与えた場合の処理時間は、逆にそれぞれほぼ 2 倍になりました。 つまり、いずれの場合においても、二分挿入ソートのほうが単純挿入ソートよりも速かったわけです。
しかも、母数 (配列の要素の数) をいろいろ変えて試してみたりもしたのですが、処理時間の比率はいつもだいたい約 1.4 倍差となるように感じられました。 つまり、言い換えますと、本件においては、二分挿入ソートは単純挿入ソートよりも約 1.4 倍ほど速いという感じでしょうか。 これは、根拠のない勝手な推測ですが、もしかしたら、ひょっとしたら、この比率は √2 に収束するとか何とか、そういう可能性はありそうでしょうか。
