時間測定プログラムについて 至急お願いします。

[neko]

シェルソートの時間測定プログラムを作りたいのですが、#define MAX 1000とmain()の間に何を入れればいいですが？
教えてください。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 1000


main()
{
	int i,x[MAX],n;
	time_t start,end;
	srand(99);
	for(i=0;i<MAX;i++) x[i] = rand() % MAX;
	n = MAX;
	start = clock();
	shell_sort(x,n);
	end = clock();
	printf("sort\n");
	for(i = 0;i < n;i++)
		if(i==i/100*100)printf("%d\n",x[i]);
		printf("exec time:%lf sec\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
		return 0;
	}

[沖 滉均]

http://dixq.net/forum/viewtopic.php?f=3&t=7529
nekoさん、こちらの問題を放置されているようですが解決していないのであれば、
新しいトピックをたてずにあちらで継続しましょう。

[neko]

こちらでお願いします

[neko]

至急お願いします

[kimuchi]

shell_sort(x,n)
の定義が無いようです。

あと、急がれる理由と期日を明確にした方が皆さん力になって下さると思います。

[Dixq (管理人)]

> nekoさん

利用される際はどうか利用規約に従ったご利用をお願いします。
それはnekoさんのためにもなる話です。
私たち回答者はnekoさん達からお金をもらって回答しているわけではありません。
つまり回答するのはただの善意であるか、もしくは自己啓発の一環であるか、その程度だと思います。
ですから、「よし、回答を書こう」という気にさせる質問をすることこそ上手な質問の仕方だと言えましょう。
そのような投稿をすれば質問をした方も沢山回答が来てWin、回答者も気分よく回答が出来てWin、互いに利益ある関係が築けます。
しかし今回の投稿のように、投げやりにも思える投稿だと恐らく多くの回答を期待するのは難しい状況になってしまうことでしょう。

例えば、せっかくboxさんが回答を付けて下さったトピックをあのように閉じられては、
次にnekoさんに善意で協力しようという気になるでしょうか。

義理も無いのにこのようなことを言ってすみません、対応についての要望が何件か寄せられていたので苦言を呈しましたが、
もしご理解いただければ、対応後、また来ていただければ幸いに思います。

さて、このままでは気分が悪いと思いますので早速課題に取り掛かりましょう。
まず、フォーラムルールに従って投稿してもらえますか？

「シェルソート」でググれば沢山サンプルが出てくると思います。
shell_sort(x,n);を実装したいという事ですよね。
サンプルを見ながらどこまで作れそうですか？
また、for文内のprintfが少しおかしいです。確認して見て下さい。

[neko]

シェルソートのほかにも、選択ソートやバブルソート、挿入ソートがあるのですが、全然わかりません。
どうしても今日中に理解したかったのですが・・・・
失礼なことしてすみませんでした。
今後は気をつけます

[沖 滉均]

まず、フォーラムルールに従って投稿してもらえますか？

と、ありますように以下テンプレートで、質問を書いていただけないでしょうか？
現在の状態ですと的確な回答は出来かねます。

前のトピックでboxさんが書かれている内容と、kimuchiさんが書かれているよう、
shell_sort(x,n)の実装についてもお答えいただけると幸いです。
もし、出来ていないのであれば、その旨書いていただければ良いと思います。

以下、フォーラムルールより引用
[1] 質問文
　[1.1] 自分が今行いたい事は何か
　[1.2] どのように取り組んだか(プログラムコードがある場合記載)
　[1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)
　[1.4] 今何がわからないのか、知りたいのか

[2] 環境 　
　[2.1] OS ： Windows, Linux等々
　[2.2] コンパイラ名 ： VC++ 2008EE, Borand C++, gcc等々

[3] その他
　・どの程度Ｃ言語を理解しているか
　・ライブラリを使っている場合は何を使っているか

[kimuchi]

とりあえずシェルソートで時間を計測できるコードを書いてみました。
参考：
http://ja.wikipedia.org/wiki/%E3%82%B7% ... C%E3%83%88
http://ja.wikipedia.org/wiki/%E6%8C%BF% ... C%E3%83%88

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//記録が出なかったので増加
#define MAX 32768

//探索間隔数列のｎ（適当）
int hn=40;
//原理は挿入ソート
int shell_sort(int (*data)[MAX],int n,int h){
	int i,j,tmp;
	for (i = 1; i < n; i++) {
		tmp = (*data)[i];
		if(i-h<0) continue;
		if ((*data)[i-h] > tmp) {
			j = i;
			do {
				(*data)[j] = (*data)[j-h];
				j-=h;
			} while (j-h >= 0 && (*data)[j-h] > tmp);
			(*data)[j] = tmp;
		}
	}
	hn--;
	if(hn==-1) return 0;
//間隔を狭めて再帰する
	shell_sort(data, n, 3*hn+1);
	return 0;
}

int main()
{
    int i,x[MAX],n;
    time_t start,end;
    srand(99);
    for(i=0;i<MAX;i++) x[i] = rand() % MAX;
    n = MAX;
    start = clock();
//第3引数は間隔を指定（3*hn+1で計算時間減少？）
    shell_sort(&x, n, 3*hn+1);
    end = clock();
    printf("sort\n");
    for(i = 0;i < n;i++)
        printf("%d\n",x[i]);
//doubleで計算されるよう修正
    printf("exec time:%f sec\n",(double)((end-start)*1.0/CLOCKS_PER_SEC));
    return 0;
}

[neko]

親切な対応ありがとうございます。

掲載されたコードでコンパイルしてみました。
配列の要素数を50000で測定したら途中で終わったのですが、なぜですか？

[kimuchi]

for(i=0;i<MAX;i++) x = rand() % MAX;

この部分で、signed intの扱える値が
-32768から32767だったと思うのでそれを超えるものはオーバーフローになるからです。

おそらく途中で終わった時も32767に近いものではなかったでしょうか？

[沖 滉均]

配列の要素数を50000で測定したら途中で終わったのですが、なぜですか？

コンパイラに依存する部分でもありますが大体rand()関数で取得できる値の最大値が
stdlib.hの中で
#define RAND_MAX 0x7fff
として定義されております。

0x7fffというのは10進数であらわすと32767となり最大でも0～32767の32768個のデータしか取得できないため
途中で止まっているように見えているだけで
重複した値も順番にソートされ最大値32767が最後に表示されているのだと思われます。

もし、それ以上の値を用意したいのであればrand関数を自作するか別の方法でデータを初期化してあげる必要があります。
[hr]
[追記]
kimuchiさん
signed intの範囲は32bit環境では、-2147483648～2147483647ではなかったでしょうか？
こちらも環境依存の値になりますので一概には言えませんが

[neko]

ありがとうございます。
なるほど！

当たり前ですが、選択ソートやバブルソート、挿入ソートやクイックソートだとまた違ったコードになりますよね？
参考としてあげたサイトのサンプル例をつかっていますが、うまくできません。

[沖 滉均]

参考としてあげたサイトのサンプル例をつかっていますが、うまくできません。

質問する際には、「うまくできません」だけでは何がうまくいかないのか回答者には分かりません。
何度もこういうやり取りになってしまい申し訳ありませんがフォーラムルールやテンプレートを使用するなど
回答者にも分かるように書いていただけないでしょうか？

ご自身で作成されたコードがあれば、それを貼った上でどこがどううまくいっていないのかの説明をお願いします。

[Dixq (管理人)]

> nekoさん

回答者さんがお聞きになったことはなるべく漏れなくお答え下さい。
また、boxさんに対してもあのままですし、私も沖さんもお願いしている規約に沿った投稿がなされないのはどうしてですか？

そして、今現在シェルソートを使ったプログラムを書かれていると思いますが、他のソートについても作成する必要があるのですか？
それは具体的に何ですか？
どこをどう変更してうまくいかなかったのですか？

クイックソートについては理解がなかなか難しいと思うのでこのような解説アプリを作りました。
http://dixq.net/sort.html
良ければお使いください。

[kimuchi]

＞＞沖 滉均 さん
うわ、寒さで頭が凍結していたようです。
この範囲はshort int でした；
おまけにオーバフローなんて何が起こるか分からないので原因理由としておかしいですね。

ご助言ありがとうございました。そしてスレ汚し失礼いたしました。