Ｃ言語 ソートについて

質問

#include <stdio.h>
#include <stdbool.h>
#define NUM_ARRAY 4
#define NUM_DATA 5
int count_swap = 0; // 交換回数 int count_comparison = 0; // 比較回数
void selection_sort(int a[], int n) {
}
int main(void) {
int data[NUM_ARRAY][NUM_DATA] =
{{9, 7, 5, 6, 8},
{9, 8, 7, 6, 5},
{5, 6, 7, 8, 9},
{5, 6, 8, 7, 9}};
for (int i = 0; i < NUM_ARRAY; i++) {
count_swap = 0;
count_comparison = 0;
int d[NUM_DATA];
copy_array(data[i], d, NUM_DATA); // 配列のコピー
printf("----------------\n");
print_array(d, NUM_DATA); // ソート前の配列の表示 selection_sort(d, NUM_DATA); // 挿入ソートの実行 print_array(d, NUM_DATA); // ソート後の配列の表示
printf("比較回数: %d\n", count_comparison); // 比較回数の表示
printf("交換回数: %d\n", count_swap); // 交換回数の表示
}
}

上の雛形を使って選択ソートを実行するという問題なのですが途中までそれっぽいのは出来たのですが上手くいかないので解答をお願いします。
下に自分が今書いているものを置いておきます。

#include <stdbool.h>
#include <stdio.h>

#define NUM_ARRAY 4
#define NUM_DATA 5

int count_swap = 0;
int count_comparison = 0;

void swap(int d[], int i, int j) {
count_swap += 1;
printf("swap a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]);
int temp = d[i];
d[i] = d[j];
d[j] = temp;
}
void copy_array(int *a, int *b, int n) {
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
}
void print_array(int d[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", d[i]);
}
printf("\n");
}
bool compare(int d[], int i, int j) {
count_comparison += 1;
printf("compare a[%d] = %d, a[%d] = %d\n", i, d[i], j, d[j]);
if (d[i] > d[j]) {
return true;
} else {
return false;
}
}
void selection_sort(int d[], int n) {
int min;
for (int i = 0; i < n - 1; i++) {
min = i;
for (int j = i + 1; j < i; j++) {
if (compare(d, min, j)) {
min = j;
}
}
swap(d, i, min);
print_array(d, n);
}
}
int main(void) {
int data[NUM_ARRAY][NUM_DATA] = {
{9, 7, 5, 6, 8}, {9, 8, 7, 6, 5}, {5, 6, 7, 8, 9}, {5, 6, 8, 7, 9}};
for (int i = 0; i < NUM_ARRAY; i++) {
count_swap = 0;
count_comparison = 0;
int d[NUM_DATA];
copy_array(data[i], d, NUM_DATA); // 配列のコピー
printf("----------------\n");
print_array(d, NUM_DATA); // ソート前の配列の表⽰
selection_sort(d, NUM_DATA); // 挿⼊ソートの実⾏
print_array(d, NUM_DATA); // ソート後の配列の表⽰
printf("⽐較回数: %d\n", count_comparison); // ⽐較回数の表⽰
printf("交換回数: %d\n", count_swap); // 交換回数の表⽰
}
}

回答No.4

AsarKingChang · ベストアンサー

明日真面目に見ますが、
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < i; j++) {
この2段ループは正しいと思います。
要するに[4,3,2,1]だった場合に
「１」が「４」の位置に行く必要がある時の
最大数は、変数の長さ-1なので。
４＜＞３
３＜＞２
２＜＞１　ここで入れ替えられるが、4回目ではなく3回目だからです。

で、j=i+1なのは
４＜＞３　「３」の位置は「４」の位置の次、つまりi+1だから
ネストループはi+1で正しい。
ってのを、親ループで0~3-1（つまり0,1,2だということで）
これはあってますよ。

違和感は、minに覚える必要がなくて、単にいきなり
入れ替えればそれでよかっただけ！
それだけで実際治るとは思います。

お礼

あれから色々と試してみた結果実行結果通りに実行できました！
いつも丁寧に解説してくださって本当にありがとうございます！

回答No.5

asuncion

どんな結果がほしいんですか？

回答No.3

AsarKingChang

>swap(d, i, min); ←この位置って、常にmin=iなんだから意味がないのでは？

ここは私のミス。
サブのjループでオーバーライドされてますね。

回答No.2

AsarKingChang

まだ実際にトレースしたわけじゃないのですが、
ソース内をパッと見て、気持ち悪さを感じたところから

void selection_sort(int d[], int n) {
int min;
for (int i = 0; i < n - 1; i++) {
min = i;
for (int j = i + 1; j < i; j++) {
if (compare(d, min, j)) {　←minって常にiなんじゃ？
min = j; ←覚えるより、この時点でswapでいいんじゃ？
}
}
swap(d, i, min); ←この位置って、常にmin=iなんだから意味がないのでは？
print_array(d, n);
}
}
などが、気持ち悪く感じた部分になりますね。
ある程度プログラムをやってると（と言っても私は水商売で暇なのでやり始めた程度ですが）
「？なんか、違和感があるぞ？」って感じる時があり、
それを、気持ち悪いぞ！って表現してるんですが。
この感覚が体に染みつくと、後は結構
ほとんどの言語で、金になりますよ＾＾
JAVA系なら月１２０万以上稼げる仕事も多く、
PHP系でも、８０万とかもざらにあります。
ですが、言語が違っても、この「気持ち悪いぞ？」って
雰囲気だけで、結構いけるんですよね＾＾
もし、仕事として、勉強しているのであれば、
その感覚がいつか身に付いたらおいしいですよ！

#define NUM_ARRAY 4
#define NUM_DATA 5
void selection_sort(int d[], int n) {
これも、少し気持ち悪い系
selection_sort(d, NUM_DATA); // 挿⼊ソートの実⾏
固定値でしか呼ばないなら、このパラメータそのものがいらないね！
ってな。
ただし、後で分離する可能性があるって意思表示する為の
ソースなんだな！と認識する人が多いとは思います。
（ここは、別に間違いではない！ただ気持ち悪いだけ）

目で（脳みそ）で経路を追いかけて行ったとき、
「？」にぶつかるその時が一番楽しい時間ですよ！
プログラムって。
明日、真面目に見てみますよ。まだ解決していなかったら。

補足

色々ありがとうございます！
取り敢えず今回教えてもらったことを踏まえて自分でも取り組んでみます！

回答No.1

AsarKingChang

しばらく回答がついていないようなので、
要件定義をお願いできます？
>途中までそれっぽいのは出来たのですが上手くいかないので解答をお願いします。
それと、どうなったら正しい（検収）になるのかと。
多分簡単な事だとは思うのですが、
問題と答えがわからないので、質問者が何を
間違っているのかが判断できないもので。

補足

----------------
97568
compare a[0] = 9, a[1] = 7 swapa[1]=7, a[0]=9 79568
compare a[1] = 9, a[2] = 5 swapa[2]=5, a[1]=9 compare a[0] = 7, a[1] = 5 swapa[1]=5, a[0]=7 57968
compare a[2] = 9, a[3] = 6 swapa[3]=6, a[2]=9 compare a[1] = 7, a[2] = 6
swapa[2]=6, a[1]=7 compare a[0] = 5, a[1] = 6 56798
compare a[3] = 9, a[4] = 8 swapa[4]=8, a[3]=9 compare a[2] = 7, a[3] = 8 56789
56789
比較回数: 8
交換回数: 6
----------------
98765
compare a[0] = 9, a[1] = 8 swapa[1]=8, a[0]=9 89765
compare a[1] = 9, a[2] = 7 swapa[2]=7, a[1]=9 compare a[0] = 8, a[1] = 7 swapa[1]=7, a[0]=8 78965
compare a[2] = 9, a[3] = 6 swapa[3]=6, a[2]=9 compare a[1] = 8, a[2] = 6 swapa[2]=6, a[1]=8 compare a[0] = 7, a[1] = 6 swapa[1]=6, a[0]=7 67895
compare a[3] = 9, a[4] = 5 swapa[4]=5, a[3]=9 compare a[2] = 8, a[3] = 5 swapa[3]=5, a[2]=8 compare a[1] = 7, a[2] = 5 swapa[2]=5, a[1]=7 compare a[0] = 6, a[1] = 5 swapa[1]=5, a[0]=6 56789
56789
比較回数: 10
交換回数: 10
----------------
56789
compare a[0] = 5, a[1] = 6 56789
compare a[1] = 6, a[2] = 7 56789
compare a[2] = 7, a[3] = 8 56789
compare a[3] = 8, a[4] = 9 56789
56789
比較回数: 4
交換回数: 0
----------------
56879
compare a[0] = 5, a[1] = 6 56879
compare a[1] = 6, a[2] = 8 56879
compare a[2] = 8, a[3] = 7
swapa[3]=7, a[2]=8 compare a[1] = 6, a[2] = 7 56789
compare a[3] = 8, a[4] = 9 56789
56789
比較回数: 5
交換回数: 1

上のような実行結果になれば良いのですがcompareが表示されなくて色々試してるのですがわかりません…