単純選択ソート
昨日の日記 バブルソートのお勉強 (Nov 22, 2011) におきまして、「単純選択ソート (straight selection sort)」 と呼ばれるものについて言及いたしました。 が、その後、そこに掲載したサンプルコードにはもう少し見直しの余地がありそうだと思いまして、本日あらためて日記を書くことにしました。
昨日の単純選択ソートを少し改良してみます
昨日の日記には、わたしなりの単純選択ソートのサンプルコードとして、以下のものを掲載いたしました。
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; } }
この場合、data[i] と data[j] の交換回数は、最悪の場合は両者の比較回数と同じ (n2-n)/2 となります。 ところが、Java データ構造とアルゴリズム基礎講座 (長尾和彦著 技術評論社 2009 ISBN978-4-7741-3697-4) には、もう少しスマートなサンプルコードが載っていました。 例によって Java で書かれたコードなので、それを C で書き直してみますと、次のようになると思います。
void sort4(int data[], int length) { int i, j, min, tmp; for (i = 0; i < length - 1; i++) { min = i; for (j = i + 1; j < length; j++) if (data[min] > data[j]) min = j; tmp = data[i]; data[i] = data[min]; data[min] = tmp; } }
この場合、最も小さい値を持つ要素のインデックスを保持する目的で min という変数を導入することにより、交換回数は n に押さえることができます。 前掲書 p. 163 にもその旨の記述があったのですが、昨日の時点では見落としてしまいました。 また実際、あとで見るように、これは少なからず処理速度の高速化に寄与するようです。
ところで、単純選択ソートは、安定ソートとなることが保証されていません。 たとえば、2、2、1 と並んだ数列に対して単純選択ソートをおこなうと、まず 1 番目の 2 と 3 番目の 1 とが交換され、そこで全体がソート済みとなりますので、もともと 1 番目にあった 2 と 2 番目にあった 2 は結果的に逆順になってしまうのです。
Wikipedia 日本語版で、ソート の記事 (Jul 21, 2011) を読んでみますと、ソートアルゴリズムの一覧表の中で (「選択ソート」 を 「単純選択ソート」 のことと解釈していいのかどうかまだよくわかりませんが) 「選択ソート」 の備考欄に 「安定ソートとしても実装可能」 という注釈が見えます。 さて、単純選択ソートを安定ソートとして実装するには、どうしたらよいのでしょう。
単純選択ソートを安定ソートとして実装してみます
先ほどの、安定ソートでないバージョンの単純選択ソートのサンプルコードでは、data[i] と data[min] とを単純に交換していました。 ここを、そうではなく、data[i] から data[min - 1] までの各要素をひとつずつうしろにずらし、もともとの data[min] をもともとの data[i] の位置に持ってくることをすれば、安定ソートになるんじゃないかと思います。
実際に書いてみたのが、次のコードです。
void sort5(int data[], int length) { int i, j, min, tmp; for (i = 0; i < length - 1; i++) { min = i; for (j = i + 1; j < length; j++) if (data[min] > data[j]) min = j; tmp = data[min]; for (j = min; i < j; --j) data[j] = data[j - 1]; data[i] = tmp; } }
複数の連続した要素をひとつずつずらすという操作は、これが配列でなくリストであれば、そもそも 1 回の操作で済むところです。 この部分は、おそらく、処理速度の悪化要因にはなってしまうでしょう。 これよりももっと効率的な (というか処理速度の悪化の程度の小さい) 安定ソート化ができればいいのですが、いまのわたしにはまだちょっと思いつきません。 というか、実のことを言うと、そもそもこのコードも、本当にこれは単純選択ソートの改良版とみなしてよいのかどうか、もしかしたらもはや単純選択ソートではなく 「単純挿入ソート (straight insertion sort)」 と呼ばれるものに変質してしまったとはいえないだろうか、などという別の疑念も湧いてきますが、とりあえずいまは考えないことにさせてください。
処理速度を比較してみます
さて、sort3 (わたしの昨日の単純選択ソート) と sort4 (長尾さんの単純選択ソート) と sort5 (長尾さんの単純選択ソートをベースとしたわたしなりの安定ソート化) とで、処理速度の比較をしてみます。
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10000 void sort3(int data[], int length); void sort4(int data[], int length); void sort5(int data[], int length); int main(void) { srand(time(NULL)); int i, j, data3[N], data4[N], data5[N]; clock_t t0, t1; for (i = 0; i < 10; i++) { for (j = 0; j < N; j++) { data3[j] = rand(); data4[j] = data3[j]; data5[j] = data4[j]; } t0 = clock(); sort3(data3, N); t1 = clock(); printf("sort3 = %u, ", t1 - t0); t0 = clock(); sort4(data4, N); t1 = clock(); printf("sort4 = %u, ", t1 - t0); t0 = clock(); sort5(data5, N); t1 = clock(); printf("sort5 = %u\n", t1 - t0); } }
これを実行しますと、たとえば次のような結果を得ます。
sort3 = 473, sort4 = 206, sort5 = 302 sort3 = 470, sort4 = 205, sort5 = 300 sort3 = 470, sort4 = 204, sort5 = 306 sort3 = 468, sort4 = 205, sort5 = 301 sort3 = 471, sort4 = 205, sort5 = 328 sort3 = 495, sort4 = 211, sort5 = 304 sort3 = 481, sort4 = 211, sort5 = 306 sort3 = 478, sort4 = 207, sort5 = 304 sort3 = 475, sort4 = 212, sort5 = 317 sort3 = 465, sort4 = 205, sort5 = 306
やはり、昨日のわたしの単純選択ソートの実装コードよりも、長尾さんの実装コードのほうが、ずっと高速のようです。 交換回数が (n2-n)/2 から n に減ったのは、大きいようです。 やはり、比較回数だけでなく、交換回数も気にしないと、効率のよいソートのアルゴリズムは生まれないのでしょうね。
また、単純選択ソートの安定ソート化は、やはり複数の連続した配列をひとつずつずらすという操作が入った分だけ、それなりに低速になったといえそうです。 それでも、わたしの昨日の単純選択ソートよりはだいぶましですが。
ちなみに、上記の処理速度比較のコードは、与えられた配列の各要素はランダムな値を持っていました。 それに対して、今度は、完全に逆順でソート済みの配列を与えた場合はどうなるかという観点でも処理速度を比較してみました。 (main 関数の中で data3[j] = rand(); という部分を data3[j] = N - j; と書き直しただけですが。) その結果は、次のようになりました。
sort3 = 460, sort4 = 215, sort5 = 419 sort3 = 454, sort4 = 217, sort5 = 423 sort3 = 457, sort4 = 214, sort5 = 416 sort3 = 455, sort4 = 214, sort5 = 416 sort3 = 457, sort4 = 216, sort5 = 413 sort3 = 457, sort4 = 215, sort5 = 412 sort3 = 457, sort4 = 216, sort5 = 411 sort3 = 461, sort4 = 218, sort5 = 417 sort3 = 462, sort4 = 217, sort5 = 419 sort3 = 457, sort4 = 213, sort5 = 415
sort5 の処理速度が、だいぶ悪化しました。 逆順でソート済みの配列を与えられると、sort5 では、配列の各要素をひとつずつうしろにずらす操作の回数と最小の値を前に持ってくる操作の回数の合計が、最大の (n2-n)/2 になります。 それがそれなりのインパクトを持ったということなのでしょう。 それでもなお、わたしの昨日の単純選択ソートよりはまだましですが。
