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

Question

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

解決済

回答 1

投稿 2016/01/01 15:07

評価
クリップ 0
VIEW 1,504

sort_merge

score 16

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

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

#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という感じで表示されてしまいます。

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

クリップを取り消します
良い質問の評価を上げる

以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します

評価を下げられる数の上限に達しました

評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します

この機能は開放されていません

評価を下げる条件を満たしてません

評価を下げる理由を選択してください
プログラミングに関係のない質問やってほしいことだけを記載した丸投げの質問問題・課題が含まれていない質問意図的に内容が抹消された質問過去に投稿した質問と同じ内容の質問広告と受け取られるような投稿
詳細な説明はこちら

上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。
質問の評価を下げる機能の利用条件

この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
- メールアドレスの認証
  メールアドレスの認証
- 質問評価に関するヘルプページの閲覧
  質問評価に関するヘルプページの閲覧

回答 1 件

評価が高い順
新着順
古い順

同じタグがついた質問を見る

C

score 2 · Accepted Answer · 2016-01-01T16:05

ベストアンサー

+2

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);

投稿 2016/01/01 16:05

編集 2016/01/01 16:48

回答の評価を上げる

以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
回答の評価を下げる

下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

2016/01/01 16:38

#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

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

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

キャンセル
2016/01/01 16:49 編集

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

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

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

ちょっと書き方が足りなかったですかね。「関数プロトタイプ宣言」は、実際の関数に合わせて（コピペして）ください。それと、関数呼び出しには「引数」を指定してください。上記、回答の方に追記しました。

キャンセル
2016/01/01 17:01

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

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

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

処理時間は0(11.820917)

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

自分で手を加えてみた結果処理時間的な結果が出てきました。以下は手を加えてみた部分です。 inputdata(t,arrey); SelectionSort(t,arrey); printdata(t,arrey); mainのあとのinputdata等の()に追加してみました。処理時間は0(11.820917) このように表示されたのですが、この結果をどうグラフに反映させたらよいか教えていただけないでしょうか。

キャンセル
2016/01/01 17:19

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

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

キャンセル
2016/01/02 11:27

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

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

キャンセル

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

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

関連した質問

同じタグがついた質問を見る

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

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

15分調べてもわからないことは、teratailで質問しよう！

関連した質問

同じタグがついた質問を見る

SNSアカウントでログイン

teratailアカウントでログイン