C言語のソートの問題について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
澁谷

C言語のソートの問題について

#1

投稿記事 by 澁谷 » 1年前

コード:

 #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);        // 交換回数の表⽰
    }
}

アバター
幸尚
記事: 47
登録日時: 2年前
連絡を取る:

Re: C言語のソートの問題について

#2

投稿記事 by 幸尚 » 1年前

viewtopic.php?f=3&t=21555
こちらの問題は解決したのでしょうか?
ボールを違うところに投げてたらご指摘して頂けると嬉しいです(o_ _)o

澁谷

Re: C言語のソートの問題について

#3

投稿記事 by 澁谷 » 1年前

すみません!
あの後無事に実行できてそれを元に理解出来たのでお礼のコメントを送ったつもりですが送れてなかったです…
改めてありがとうございました!

アバター
usao
記事: 1889
登録日時: 11年前

Re: C言語のソートの問題について

#4

投稿記事 by usao » 1年前

とりあえずぱっと見で, selection_sort() 関数内にあるループ

> for (int j = i + 1; j < i; j++)

の条件がおかしいよね.
j = i+1 から始まって,ループ条件が j<i だから,いきなり条件を満たさない.


あと,今々着目している範囲の先頭要素がその範囲の最小値である場合には Swap しなくていい.
(何か Swap の回数を数えているみたいだから,ここが問われるかも?)

返信

“C言語何でも質問掲示板” へ戻る