C言語教室 第26回 - いろいろなソート（回答提出）（続）
【2023/6/6 追記】
このソート記事はイマイチ。
ソートについてはこちらも是非。
先日、こちらの課題を回答しました。
課題
文字列の配列をバブルソートで並べ替える関数を書いてください。文字列の大小比較は strcmp を使ってください。なお、文字列全体を入れ替えながらソートすると大変なので文字列へのポインタの配列を用意して、これをソートするようにしてください。
今回は続編です。
昔書いたことがあるソートロジックを今一度書いてみました。
バブルソートと同じく総当たりでチェックしますが、バブルソートと言えるのかどうかわからない。
考え方は単純。
まず一番小さい数値を探して先頭におく。
終われば次に小さい数値を探して2番目におく。
それも終わればもう一つ次に小さい数値を探して3番目におく。
それを繰り返して行きます。
30年近く前でアルゴリズム集なども見ずに書いてますから、単純この上ない(笑)。
ただ、バブルソートと比較してみると、交換回数がまったく同じなんですね。これはちょっと意外でした。どちらも総当たりですから、同じと言われればなるほどと思わないでもありません。ただ、比較する順番が違えば、場合によっては例えば小さい数値が一気に前に躍り出たりすることもあるのかなという気がしていました。そうすれば、交換回数も減るのではないか。でも、そういうわけではないようです。
まずは、２種類のソートプログラムです。
プログラム1
#include <stdio.h>
#include <stdlib.h>
int cnt = 0;
void bubble_sort(int *array, unsigned int size) {
for (int k = 0; k < size; k++) printf("%d ", array[k]);
printf("\n");
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
cnt++;
for (int k = 0; k < size; k++) printf("%d ", array[k]);
printf("\n");
}
}
}
printf("bubble_sort swaped %d\n ", cnt);
printf("\n");
}
int main() {
int data[10] = {6, 3, 8, 9, 5, 4, 1, 7, 0, 2};
unsigned int size = sizeof(data) / sizeof(data[0]);
bubble_sort(data, size);
return 0;
}プログラム2
#include <stdio.h>
#include <stdlib.h>
int cnt = 0;
void bubble_sort(int *array, unsigned int size) {
for (int k = 0; k < size; k++) printf("%d ", array[k]);
printf("\n");
for (int i = 0; i < size - 1; i++) {
for (int j = i+1; j < size; j++) {
if (array[i] > array[j]) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
cnt++;
for (int k = 0; k < size; k++) printf("%d ", array[k]);
printf("\n");
}
}
}
printf("bubble_sort swaped %d\n ", cnt);
printf("\n");
}
int main() {
int data[10] = {6, 3, 8, 9, 5, 4, 1, 7, 0, 2};
unsigned int size = sizeof(data) / sizeof(data[0]);
bubble_sort(data, size);
return 0;
}そして、それぞれの結果です。
プログラム1の結果
6 3 8 9 5 4 1 7 0 2
3 6 8 9 5 4 1 7 0 2
3 6 8 5 9 4 1 7 0 2
3 6 8 5 4 9 1 7 0 2
3 6 8 5 4 1 9 7 0 2
3 6 8 5 4 1 7 9 0 2
3 6 8 5 4 1 7 0 9 2
3 6 8 5 4 1 7 0 2 9
3 6 5 8 4 1 7 0 2 9
3 6 5 4 8 1 7 0 2 9
3 6 5 4 1 8 7 0 2 9
3 6 5 4 1 7 8 0 2 9
3 6 5 4 1 7 0 8 2 9
3 6 5 4 1 7 0 2 8 9
3 5 6 4 1 7 0 2 8 9
3 5 4 6 1 7 0 2 8 9
3 5 4 1 6 7 0 2 8 9
3 5 4 1 6 0 7 2 8 9
3 5 4 1 6 0 2 7 8 9
3 4 5 1 6 0 2 7 8 9
3 4 1 5 6 0 2 7 8 9
3 4 1 5 0 6 2 7 8 9
3 4 1 5 0 2 6 7 8 9
3 1 4 5 0 2 6 7 8 9
3 1 4 0 5 2 6 7 8 9
3 1 4 0 2 5 6 7 8 9
1 3 4 0 2 5 6 7 8 9
1 3 0 4 2 5 6 7 8 9
1 3 0 2 4 5 6 7 8 9
1 0 3 2 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
bubble_sort swaped 31プログラム2の結果
6 3 8 9 5 4 1 7 0 2
3 6 8 9 5 4 1 7 0 2
1 6 8 9 5 4 3 7 0 2
0 6 8 9 5 4 3 7 1 2
0 5 8 9 6 4 3 7 1 2
0 4 8 9 6 5 3 7 1 2
0 3 8 9 6 5 4 7 1 2
0 1 8 9 6 5 4 7 3 2
0 1 6 9 8 5 4 7 3 2
0 1 5 9 8 6 4 7 3 2
0 1 4 9 8 6 5 7 3 2
0 1 3 9 8 6 5 7 4 2
0 1 2 9 8 6 5 7 4 3
0 1 2 8 9 6 5 7 4 3
0 1 2 6 9 8 5 7 4 3
0 1 2 5 9 8 6 7 4 3
0 1 2 4 9 8 6 7 5 3
0 1 2 3 9 8 6 7 5 4
0 1 2 3 8 9 6 7 5 4
0 1 2 3 6 9 8 7 5 4
0 1 2 3 5 9 8 7 6 4
0 1 2 3 4 9 8 7 6 5
0 1 2 3 4 8 9 7 6 5
0 1 2 3 4 7 9 8 6 5
0 1 2 3 4 6 9 8 7 5
0 1 2 3 4 5 9 8 7 6
0 1 2 3 4 5 8 9 7 6
0 1 2 3 4 5 7 9 8 6
0 1 2 3 4 5 6 9 8 7
0 1 2 3 4 5 6 8 9 7
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
bubble_sort swaped 31プログラム1の結果を見ると、2行目あたりから9が1つずつ右にずれていってるのがわります。このプログラムは、
大きい数値を少しずつ後ろにずらす
というやり方。
一方、プログラム2の結果では、3行目でいきなり0が先頭になります。
こちらは
小さい数値から順に並べていく
というやり方。
プログラム2では3回の交換で0が先頭に立つんですね。そうすると、なんだかこちらの方が交換回数は少なくて済みそうにも思えるんですが、効果回数はどちらも31回と全く同じ。ソート数を増やせばどうかと言うと、乱数100個で交換回数は2289回と、この場合も全く同じ。乱数100個、2289回が同じというのは偶然とは考えにくい。数学的に証明できることなのかもしれません（知らんけど）。
Wikiには次のようにあります。
この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ（安定ソート）。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。
『安定ソート』と『比較交換順序を調整することで効率化され』がイマイチわからない(笑)。『順序を問わない』んだから、『交換順序を調整』しても同じなんじゃないか。と思うのは浅はかか。
ま、いいか。
この記事が気に入ったらサポートをしてみませんか？