シェルソートの計算量

質問

nから降順で並べたソートをシェルソートで並び替える場合、計算量はどうなるのかを求めるプログラム（C言語）を教えてください。

回答No.6

Trick--x--

#include <time.h>
Sort(); //プロトタイプ
main()
{
time_t stime,etime;
double dtime;
stime = time(NULL);
Sort();
etime = time(NULL);
dtime = difftime(etime,stime);
}
dtimeに秒単位でかかった時間が入ります。
Sortからは余計な処理（画面表示、入力など）は抜くこと。
これでどう？

回答No.5

hpsk

シェルソートに関しては，アルゴリズムは理解されているように見受けられますので，「書いてみたものこここがうまくいかない」という質問のほうが良いと思います．
もっとも，適当に検索すればそのものズバリのものがいくらでも転がっていますが．

時間獲得の方法に関しては，#4の方のおっしゃる通り環境（OS，コンパイラ）を書いていただかないと何ともいえません．

補足

シェルソートに関しては完成、かつ正常に動きましたので大丈夫です。

OSはWindowsXP、コンパイラはbcc32.exeです。環境によって方法等も変わってくるものなのでしょうか？

回答No.4

Trick--x--

環境によるのかな……
そのプログラム（関数）の実行前後でtimeを取って、その差を見るのは出来ない？

補足

やはり環境によって違いが出てきますか(^^;

回答No.3

gakutensoku

補足を2点ほどお願いします。

(1)シェルソートのプログラムその物は既にあるのですよね?

(2)No.2の補足に「具体的な数列を与えてそれをソートするためにかかった時間」とありますが、求めたいのは時間でよいですか？(比較回数/交換回数ではなく。)

補足

>(1)シェルソートのプログラムその物は既にあるのですよね?
一応、それらしき物は作っていますが、できればお願いします

>(2)No.2の補足に「具体的な数列を与えてそれをソートするためにかかった時間」とありますが、求めたいのは時間でよいですか？(比較回数/交換回数ではなく。)
時間のみです。

かなりお手数をおかけしていますが、よろしくお願いします

回答No.2

hpsk

うーん，やはりいまいちよくわかりません．
とはいってもいくつかの予測はつきますが．

まず，「シェルソートの計算量を求める」と言ったばあい，具体的な数列を与えてそれをソートするためにかかった時間や比較回数，交換回数を出力する，ということではなくて．
最悪の場合nに対してこれだけの時間がかかる，平均的にはこれだけの時間がかかる，というこを数学的に示すことを指します．
質問者さまのおっしゃりたいことは前者だと思いますが，いかがでしょう？

> 降順に並べた整数の列をシェルソートで並び替えた
文字通りに解釈すると
「降順に並んでるんだったらソートしなくてもいいじゃん」
となります．
整数の列を，降順にソートするのですか？

補足

>「シェルソートの計算量を求める」と言ったばあい，>具体的な数列を与えてそれをソートするためにかかっ>た時間や比較回数，交換回数を出力する，ということ>ではなくて．最悪の場合nに対してこれだけの時間が
>かかる，平均的にはこれだけの時間がかかる，という>こを数学的に示すことを指します．
すいません。すっかり勘違いしてしまいました。「具体的な数列を与えてそれをソートするためにかかっ>た時間」を求めるプログラムです。「シェルソートの計算量を求める」ですと最悪計算量O(n^2)になってしまいますね。。

> 降順に並べた整数の列をシェルソートで並び替えた
>文字通りに解釈すると「降順に並んでるんだったらソ>ートしなくてもいいじゃん」となります．
うまく説明できないので例を・・・
5 4 3 2 1
↓並び替え
1 2 3 4 5
こういった形で結果を導き出したいのですが。。。

どうでしょうか？

回答No.1

hpsk

> 計算量はどうなるのか
シェルソートの最悪計算量は O(n^2) です．
それを求めるプログラムを作るのですか？

> nから降順で並べたソートをシェルソートで並び替える
というのもいまいち意味がわかりません．

補足

すいません。かなり言葉が足りていないようです。
> 計算量はどうなるのか
降順に並べた整数の列をシェルソートで並び替えた場合の計算量を導き出すというプログラムを作りたいです。

> nから降順で並べたソートをシェルソートで並び替える
整数の列の例ということで書いてました。無視してください。

分かりにくい補足ですが、お願いします。