直接選択法によるソートの様子とソートに必要な比較回数と交換回数を数える

前提・実現したいこと

C言語で直接選択法によるソートの様子とソートに必要な比較回数と交換回数を数えるプログラムを作成したいです。とりあえず、直接選択法によるソートはできたのですが、可視化するにはどのようにプログラムを組めばよいかわかりません。

該当のソースコード

#include <stdio.h>

#define N 6

void main(void)
{
    int a[]={80,41,35,90,40,20};
    int min,s,t,i,j;

    for (i=0;i<N-1;i++){
        min=a[i];
        s=i;
        for (j=i+1;j<N;j++){
            if (a[j]<min){
                min=a[j];
                s=j;
            }
        }
        t=a[i]; a[i]=a[s]; a[s]=t;
    }

    for (i=0;i<N;i++)
        printf("%d ",a[i]);
    printf("\n");
}

試したこと

int内の文字の定義を増やして、printfで出力しようとしたのですが上手くいきませんでした。

jimbe

2021/06/22 14:37

> ソートの様子とソートに必要な比較回数と交換回数の表示を追加した結果どのような表示になるとお考えなのか、"具体的に"教えて頂けますか。

Na_ma6565

2021/06/22 14:41

80 41 35 90 40 20 20 41 35 90 40 80 20 35 41 90 40 80 20 35 40 90 41 80 20 35 40 41 90 80 20 35 40 41 80 90 比較回数：15，交換回数：5 このようになるのを想定しています。よろしくお願いします。

jimbe

2021/06/22 14:50

順番に見ていきましょう。まず、最初の6行が"ソートの様子"ということですね。現状はその6行のうち最後の行(=ソート結果)だけが表示されているものと思います。このソート結果を表示しているのはプログラムのどの行かはご理解されていますでしょうか。

Na_ma6565

2021/06/22 14:56

最後のprintf2つだと思います。

jimbe

2021/06/22 15:15

> 最後のprintf2つでは残念ながら正確では無いと思います。一つ目の printf が個々の数値を表示していますので、その前の for 文も含めて > for (i=0;i<N;i++) > printf("%d ",a[i]); > printf("\n"); この3行で行っているとお考えになる方が良いかと思います。ですので、この3行をコピーして、一回ずつ交換を行う for ループの必要な場所にペーストすれば、交換の様子を表示できるのではないでしょうか。ただしここで注意が必要なのは、for ループで使用している変数です。 for ループの中に別の for ループを入れる場合、(特にコピペで編集していると)二つの for ループで使用している変数が同じになってしまって意図しない動作(=バグ)となる場合があります。「int内の文字の定義を増やして」との表記は「変数を増やして」ということを見ましたが、変数の理解がどこまでされているのかに疑問が生じています。この辺りを注意しながら"交換の様子"を入れてみては如何でしょうか。

Na_ma6565

2021/06/22 15:18

ありがとうございます。一度考えてみます。

行動規範の内容に同意します

回答2件

ベストアンサー

C
1#include <stdio.h>
2
3#define N 6
4
5int comps; // 比較回数
6int swaps; // 交換回数
7
8// 比較関数
9int comp(int x, int y) {
10  ++comps;
11  return x < y;
12}
13
14// 交換関数
15void swap(int* px, int* py) {
16  ++swaps;
17  int tmp = *px;
18  *px = *py;
19  *py = tmp;
20}
21
22int main(void) {
23    int a[]={80,41,35,90,40,20};
24    int min,s,t,i,j;
25
26    comps = 0;
27    swaps = 0;
28
29    for (i=0;i<N-1;i++) {
30        min=a[i];
31        s=i;
32        for (j=i+1;j<N;j++){
33            if ( comp(a[j], min) < 0 ) { // ここで比較
34                min=a[j];
35                s=j;
36            }
37        }
38        swap(&a[i], &a[s]); // ここで交換
39    }
40
41    for (i=0;i<N;i++)
42        printf("%d ",a[i]);
43    printf("\n");
44
45    printf("%d comps / %d swaps\n", comps, swaps);
46    return 0;
47}