ソートの時間計算量を比較したいのですがうまくいきません。

Question

選択法や挿入法、マージソートやクイックソートの時間計算量の比較をしたいのですが、思うように時間計算量を出すことができません。

自分が書いた選択法のソースです。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MAX 1000000
int main(){
  int arrey[MAX],t = MAX;
  int inputdata();
  struct timeval start_timeval, end_timeval;
  double sec_timeofday;
  gettimeofday( &start_timeval, NULL);
  int SelectionSort();
  gettimeofday( &end_timeval, NULL);
  sec_timeofday = (end_timeval.tv_sec - start_timeval.tv_sec) + (end_timeval.tv_usec - start_timeval.tv_usec)/ 1000000.0;
  int printdata();
  printf("処理時間0(%f)",sec_timeofday);
}

int inputdata(int t,int arrey[]){
  int i;
  srand((unsigned)time(NULL));
  printf("適当に並べられた数列-------\n");
  for(i=0; i<=t; i++){
    arrey[i] = (rand()%100+1);
    printf("arrey[%d]=%d\t",i,arrey[i]);
  }
  return(0);
}

int SelectionSort(int t,int arrey[]){
  int p,q,x,y,min;
  for(p=0; p<=t-1; p++){
    min=p;
    x=arrey[min];
    for(q=p+1; q<=t; q++){
      if(arrey[min]>arrey[q]){
	arrey[min]=arrey[q];
	y=q;
      }
    }

    arrey[p]=arrey[min];
    arrey[y]=x;
  }
  return(0);
}

int printdata(int t,int arrey[]){
  int g;
  printf("\n選択法の結果----------\n");
  for(g=0; g<=t; g++)
    printf("arrey[%d]=%d\t",g,arrey[g]);
  return(0);
}
コード

このソースを実行すると、時間計算量が0.000000や0.000001という感じで表示されてしまいます。

乱数を使ってデータの入力をしたのですが、データの入力がされてないように思えます。

アドバイスどうかお願いします。

Answer 1

int inputdata();

int SelectionSort();

int printdata();

main関数内のこれらの記述は「関数プロトタイプ宣言」とみなされて、関数呼び出しは行われません。余計なintを外してください。各関数の実装を見ると戻り値に意味はなさそうなので、voidにしてしまった方が良いかもしれません。
また、それだけだとコンパイルが通らないので、**「main関数の前」**で上記関数のプロトタイプ宣言を記述してください。

---

関数プロトタイプ宣言

void inputdata(int t,int arrey[]);
void SelectionSort(int t,int arrey[]);
void printdata(int t,int arrey[]);

関数呼び出し

inputdata(t, arrey);

SelectionSort(t, arrey);

printdata(t, arrey);

Comments

[sort_merge]

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MAX 100000
void inputdata();
void SelectionSort();
void printdata();
int main(){
int arrey[MAX],t = MAX;
inputdata();
struct timeval start_timeval, end_timeval;
double sec_timeofday;
gettimeofday( &start_timeval, NULL);
SelectionSort();
gettimeofday( &end_timeval, NULL);
sec_timeofday = (end_timeval.tv_sec - start_timeval.tv_sec) + (end_timeval.tv_usec - start_timeval.tv_usec)/ 1000000.0;
printdata();
printf("処理時間0(%f)",sec_timeofday);
}

void inputdata(int t,int arrey[]){
int i;
srand((unsigned)time(NULL));
printf("適当に並べられた数列-------\n");
for(i=0; i<=t; i++){
arrey[i] = (rand()%100+1);
printf("arrey[%d]=%d\t",i,arrey[i]);
}
return;
}

void SelectionSort(int t,int arrey[]){
int p,q,x,y,min;
for(p=0; p<=t-1; p++){
min=p;
x=arrey[min];
for(q=p+1; q<=t; q++){
if(arrey[min]>arrey[q]){
arrey[min]=arrey[q];
y=q;
}
}

arrey[p]=arrey[min];
arrey[y]=x;
}
return;
}

void printdata(int t,int arrey[]){
int g;
printf("\n選択法の結果----------\n");
for(g=0; g<=t; g++)
printf("arrey[%d]=%d\t",g,arrey[g]);
return;
}

このように書き直してみたら、実行結果がおかしくなってしまいました。
何度実行しても、

適当に並べられた数列---------
Segmentation fault: 11

このような結果が出てしまいます。
どこを直したら良いか教えていただきたいです。
何度も申し訳ありません。

[catsforepaw]

ちょっと書き方が足りなかったですかね。

「関数プロトタイプ宣言」は、実際の関数に合わせて（コピペして）ください。
それと、関数呼び出しには「引数」を指定してください。

上記、回答の方に追記しました。

[sort_merge]

自分で手を加えてみた結果処理時間的な結果が出てきました。

以下は手を加えてみた部分です。
inputdata(t,arrey);
SelectionSort(t,arrey);
printdata(t,arrey);

mainのあとのinputdata等の()に追加してみました。

処理時間は0(11.820917)

このように表示されたのですが、この結果をどうグラフに反映させたらよいか教えていただけないでしょうか。

[catsforepaw]

どういうグラフを作りたいのかが判らないのでなんとも答えられないのですが……。
それに、グラフ作りとなると本件のご質問の範疇からは外れますので、まずはどういうことをしたいのかを明確にしてプログラムの実行結果から得られた情報をどう使うのかを考え、もし判らないことがあれば新たに質問した方がよろしいかと思います。

[sort_merge]

わかりました。
細かいことまで教えていただき本当にありがとうございます。