（蛇足編、その３）C言語教室 第26回 - いろいろなソート - バブルソート、選択ソート、挿入ソート、シェルソート、マージソート、クイックソート
ソートアルゴリズムのレスポンスは、（当然ではありますが）値の交換回数だけではなく、その他の処理の効率性にも影響を受けます。
様々なソートアルゴリズムのふるまいについて、もう少し検証してみます。
※Ayumiさん情報によりますと、以前の記事で公開していた選択ソートロジックが誤っているということですので、今回の記事でアップデートしました。ご指摘有難うございます。
実行結果例
サンプル数100,000で、サンプルの種類を100,000とした場合
ランダムな整数値の配列を作成し、別に用意した配列にコピーしておきます。これをそれぞれのソートアルゴリズムで並べ替えて、その結果を相互に比較チェックします。each sorted results are same.とありますのは、全てのソートアルゴリズムの並べ替え結果が完全に一致したことを示しています。
jm3nrhMac-mini-:c akio$ ./a.out 100000 100000
Sample size = 100,000 / number of data types = 100,000
bubble sort ---- swapped: 2,504,414,108 looped: 4,999,950,000 elapsed: 23.7458 sec.
selection sort - swapped: 99,987 looped: 4,999,950,000 elapsed: 10.2700 sec.
insertion sort - swapped: 2,504,414,108 looped: 99,999 elapsed: 5.1646 sec.
shell sort ----- swapped: 2,867,686 looped: 955,719 elapsed: 0.0213 sec.
merge sort ----- swapped: 898,706 looped: 1,668,928 elapsed: 0.0129 sec.
quick sort ----- swapped: 370,853 looped: 480,947 elapsed: 0.0094 sec.
each sorted results are same.
Sort again with sorted data.
bubble sort ---- swapped: 0 looped: 4,999,950,000 elapsed: 10.2170 sec.
selection sort - swapped: 0 looped: 4,999,950,000 elapsed: 10.2247 sec.
insertion sort - swapped: 0 looped: 99,999 elapsed: 0.0002 sec.
shell sort ----- swapped: 0 looped: 955,719 elapsed: 0.0021 sec.
merge sort ----- swapped: 970,490 looped: 1,668,928 elapsed: 0.0065 sec.
quick sort ----- swapped: 0 looped: 104,534 elapsed: 0.0020 sec.
each sorted results are same.バブルソートと選択ソートは、同じ回数分の比較処理をしているようですが、選択ソートの方が値の置換回数は少なくて済んでいます。
挿入ソートは、比較処理回数よりも値の交換回数の方が多いですが、挿入地点まで値をずらすというロジックの特性に基づくものです。
値の交換回数はバブルソートと同じですが、比較処理回数は圧倒的に少ないので、CPU時間は少なくて済んでいます。
（値を入れ替えるというよりも、適切な位置に挿入して他をずらすというロジックなので、値の交換回数をどうカウントするか悩みどころ.
挿入ソートの進化系であるシェルソートは、比較処理回数は10倍近く増えていますが、値の交換処理は100分の1以下で済んでいます。
比較範囲を広げて比較するので、全体的に大まかにソートされた状態で挿入ソートが開始されるので、結果的に効率が高いと理解しました。
クイックソートは、圧倒的ですが、ソート済みのデータを与えると、処理を終わるのが挿入ソートよりも遅いという面白い結果となりました。
クイックソートを除くソートアルゴリズムは、サンプルデータの状況に関わらず同じ回数ループ処理をしているようです。
マージソートでは、値をグループ分けして大小比較しながら並べ替えるので、実際にソート済のデータを与えても値を置換する作業が発生します。
ソート結果を再度ソートしているのは、値の置換以外の処理の効率性を見ることを意図しています。バブルソートと選択ソートは、他のソートアルゴリズムと比べて無駄に値の比較処理をしていると言えそうです。
サンプル数100,000で、サンプルデータの種類を10とした場合
jm3nrhMac-mini-:c akio$ ./a.out 100000 10
Sample size = 100,000 / number of data types = 10
bubble sort ---- swapped: 2,252,829,463 looped: 4,999,950,000 elapsed: 23.3398 sec.
selection sort - swapped: 90,087 looped: 4,999,950,000 elapsed: 10.2369 sec.
insertion sort - swapped: 2,252,829,463 looped: 99,999 elapsed: 4.6316 sec.
shell sort ----- swapped: 403,802 looped: 955,719 elapsed: 0.0067 sec.
merge sort ----- swapped: 968,292 looped: 1,668,928 elapsed: 0.0088 sec.
quick sort ----- swapped: 109,029 looped: 760,127 elapsed: 0.0043 sec.
each sorted results are same.
Sort again with sorted data.
bubble sort ---- swapped: 0 looped: 4,999,950,000 elapsed: 10.2092 sec.
selection sort - swapped: 0 looped: 4,999,950,000 elapsed: 10.2362 sec.
insertion sort - swapped: 0 looped: 99,999 elapsed: 0.0002 sec.
shell sort ----- swapped: 0 looped: 955,719 elapsed: 0.0021 sec.
merge sort ----- swapped: 1,554,990 looped: 1,668,928 elapsed: 0.0065 sec.
quick sort ----- swapped: 0 looped: 698,570 elapsed: 0.0022 sec.
each sorted results are same.サンプルデータの種類を減らすと、シェルソートの効率が目に見えてよくなりました。
サンプルの種類を減らすと、マージソートの値の交換回数が増えています。うーん、不思議だ。
以上は値の交換回数、比較処理回数、CPU時間を比較して見ましたが、それぞれのソートロジックにおいて何を「値の交換」と見るか等々、異論はあると思います。お気づきの点がありましたご指摘いただけると幸いです。
検証したソートアルゴリズム
バブルソート
void swap (int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
counter++;
}
void bubble_sort (int array[], int array_size) {
for (int i = 0; i < array_size -1; i++) {
for (int j = 0; j < array_size - i - 1; j++) {
loop_count++;
if (array[j] > array[j + 1]) {
swap(&array[j], &array[j + 1]);
}
}
}
}選択ソート
void selection_sort (int array[], int array_size) {
int min;
for (int i = 0; i < array_size - 1; i++) {
min = i;
for (int j = i + 1; j < array_size; j++) {
loop_count++;
if (array[min] > array[j]) {
min = j;
}
}
if (min != i) {
swap(&array[i], &array[min]);
}
}
}挿入ソート
void insertion_sort(int array[], int array_size) {
for (int i = 1; i < array_size; i++) {
loop_count++;
if (array[i - 1] > array[i]) {
int j = i;
int tmp = array[i];
do {
counter++;
array[j] = array[j - 1];
j--;
} while (j > 0 && array[j - 1] > tmp);
array[j] = tmp;
}
}
}シェルソート
void shell_sort (int array[], int array_size) {
int i, j, h;
for (h = 1; h <= array_size / 9; h = 3 * h + 1) {} // 間隔hを決める
for ( ; h > 0; h /= 3) { // hを狭めていく
for (i = h; i < array_size; i++) {
loop_count++;
j = i;
while ((j > h - 1) && (array[j - h] > array[j])) {
swap(&array[j - h], &array[j]);
j -= h;
}
}
}
}マージソート
void merge_sort(int array[ ], int left, int right)
{
int mid, i, j, k;
int temp[right];
if (left >= right) { return; }
mid = (left + right) / 2;
merge_sort(array, left, mid);
merge_sort(array, mid + 1, right);
for (i = left; i <= mid; i++) { temp[i] = array[i]; }
for (i = mid + 1, j = right; i <= right; i++, j--) { temp[i] = array[j]; }
i = left;
j = right;
for (k = left; k <= right; k++) {
loop_count++;
if (temp[i] <= temp[j]) {
array[k] = temp[i++];
counter++;
} else {
array[k] = temp[j--];
}
}
}クイックソート
void quick_sort(int array[ ], int left, int right) {
int i, j;
int pivot;
i = left;
j = right;
pivot = array[(left + right) / 2];
while (1) {
loop_count++;
while (array[i] < pivot) { i++; }
while (pivot < array[j]) { j--; }
if (i >= j) { break; }
if (array[i] > array[j] ) {
swap(&array[i], &array[j]);
}
i++;
j--;
}
if (left < i - 1) { quick_sort(array, left, i - 1); }
if (j + 1 < right) { quick_sort(array, j + 1, right); }
}ソースコード
後記
一部のコードで再帰呼び出しを実施しています。
久しぶりだったので頭がなかなかついていけません。
各ソートアルゴリズムの実行前後で配列要素をダンプ出力したり、変数の値を表示させたりして動作を確認しました。
※シェルソートについてはまだ、ちょっとついていけてないところがあります。
ここまで読んでいただき、有難うございました。
これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。