ソートアルゴリズム

質問

お忙しいところすいません。
先日授業で出された課題がどうしても分からなかったので教えていただきたいと思っています。
どうやってプログラムを作ればよいでしょうか。

問題は、
『Ｎ件の乱数データを用意し、昇順(または降順)に並べる。
データ件数、ソート所用時間を表示する。
ソート時間１～１００秒で処理できるデータ件数を確認する。
ソートアルゴリズムは２種以上作成すること。』
です。

回答No.3

NEKOGABURI · ベストアンサー

バブルソート、挿入ソートとかでアルゴリズムは調べてください。

時間を出さないといけないのが面倒ですね。単純なのは配列長を増やして
いきながら、時間を計測してファイルに書き出し１００秒を超えた時点で終了
したらどうでしょう。

ソートの部分を関数化して、その前後でGetSystemTimeを使って経過時間を
算出して個数と経過時間をファイルに書いてそれが１００秒以上だったら終了。
使うのは、do{　前述の処理　}while（～）；

１秒から１００秒という事なら１秒以下はファイル書き出しから条件分岐で弾き
ましょう。

ソートの関数の引数は、ソートする配列長・ソートする配列へのポインタでい
いんじゃないでしょうか。

<<do、whileループの中ですること>>
前処理：配列長を初期化例えば,length=10
１．配列確保、malloc関数で動的配列確保。
　　int *ptr;
　　ptr=(int *)malloc(sizeof(int)*length);　<==　intの配列を用意したい場合
double *ptr;
　　ptr=(double *)malloc(sizeof(double)*length);　<==　doubleの配列を用意したい場合
　　以降、ptr[～]の様に普通の配列として使えます。

２．作った配列に乱数設定
　　ループの中でptr[i]＝rand()%100;って感じで。

３．GetSystemTimeで現在の開始時ののシステム時間を取得。

４．ソートの関数呼び出し

５．GetSystemTimeで現在の終了時ののシステム時間を取得。

６．開始時と終了時の時間差を計算。

７．時間差が１～１００ならファイルに書き出し。

８．free(ptr)でメモリ開放。

とこんな感じです。時間計算は他の方法もあります。

time、difftimeとGetSystemTimeはどっちでもいいです。
time、difftime　　　<==　<time.h>
GetSystemTime <== <windows.h>

出来そうですか？余裕があるならqsort関数と自分の作ったソート関数の速度差を計算してみるといいと思います。大雑把な流れだけの説明ですが、出来そうですか？再質問受け付けます。

※お礼といってはなんですが、以下のアンケートにご協力下さい。

参考URL：

http://oshiete1.goo.ne.jp/qa4815745.html

回答No.4

NEKOGABURI

うっかり！！！忘れてました。

９．として、length++を追加して置いてください。

※データ採取中なので、以下のアンケートに協力して頂けると嬉しいなぁ・・・。
宜しくお願いいたします。協力して頂けると、更に詳しく・・・。
http://oshiete1.goo.ne.jp/qa4815745.html
http://oshiete1.goo.ne.jp/qa4818502.html

回答No.2

negi-pawn

すみません、下の回答URLから最後の"＞"外してください。。。

回答No.1

negi-pawn

作業の流れとしては以下のような感じになりますかね。
(1)使用するアルゴリズムを決める
(2)決めたアルゴリズムでN件のデータをソートするプログラムを作る
(3)プログラムを実行して、結果を集計する

もうちょっと噛み砕くと以下のようになるでしょうか。
(1)ソートのアルゴリズムはいろいろあります。
<http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88>
最も処理が早いとされているのは"クイックソート"
直感的に思いつくのは"バブルソート"
あたりがわかりやすいでしょうか。好みで選べばOKだと思います。

(2)きっとここが難関ですよね。。（＞＿＜；
以下のサイトではソートのアルゴリズムがいくつかjavaで書かれていますので参考になると思います
<http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/>
以下のサイトでは実行時間の測定方法が出てるので参考にしてはいかがでしょうか
<http://kzk9.net/column/time.html>

(3)ここまでくれば終わったも同然ですよね(笑)
では

お礼

すいません。
補足のところにお礼を書いてしまいました!!!!笑

ありがとうございました。

補足

すごく丁寧なお返事ありがとうございました。
本当に助かりました。
頑張ってやってみます。