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

Question

前提・実現したいこと

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で出力しようとしたのですが上手くいきませんでした。

Comments

[jimbe]

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

[Na_ma6565]

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]

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

[Na_ma6565]

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

[jimbe]

> 最後の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]

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

Answer 1

#include <stdio.h>

#define N 6

int comps; // 比較回数
int swaps; // 交換回数

// 比較関数
int comp(int x, int y) {
  ++comps;
  return x < y;
}

// 交換関数
void swap(int* px, int* py) {
  ++swaps;
  int tmp = *px;
  *px = *py;
  *py = tmp;
}

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

    comps = 0;
    swaps = 0;

    for (i=0;i<N-1;i++) {
        min=a[i];
        s=i;
        for (j=i+1;j<N;j++){
            if ( comp(a[j], min) < 0 ) { // ここで比較
                min=a[j];
                s=j;
            }
        }
        swap(&a[i], &a[s]); // ここで交換
    }

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

    printf("%d comps / %d swaps\n", comps, swaps);
    return 0;
}

Comments

[Na_ma6565]

ありがとうございます。

Answer 2

これ がコタエになってますか?

Comments

[Na_ma6565]

参考にしてみようと思ったのですが、わかりませんでした。
すみません。

[episteme]

比較と交換を関数化し、それぞれの中で勘定してるだけなんですけど...

[episteme]

回答しました。