←検索窓の楽しみ方
  ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.4363

アルゴリズム(シェルソート)
投稿者---shu(n)ji(n)(2005/07/22 23:14:19)


シェルソートのプログラムを何とか書きました。
分割の方法はE.D.Knuthさんの方法で、
N個のデータをd分割に分けるとき、それぞれのdは

d_{t-1} = 2d_t + 1 ←漸化式
d_t=1
t = (log_2 N の小数点以下切捨て) -1

例えば Nが1000だったら
t= 8
d_8 = 1, d_7=3
d_6 = 7, d_5=15
d_4 = 31,d_3=63
d_2 = 127, d_1=255
最初に255分割、次に127分割・・・最後に1分割するという
方法で、これが一番効率がいいとされているらしいので
それを利用しています。

↓のプログラムのアルゴリズムを
文章にしていただけないでしょうか。
僕には複雑すぎて混乱しているので、お願いしますm(__)m

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define N 100
#define T 30

int shellsort (int);
int d_calc(void);
int d[N];
int data[N];
int comparison = 0;
float comp_sum = 0;
float comp_ave = 0;

main()
{
int i, loop=1;
int t;

srand(time(NULL));

while(loop<=T)
{
for(i=0; i<N; i++)
{
data[i] = rand() % 1000+1;
printf("%4d ",data[i]);
}
t = d_calc();
shellsort(t);

for(i=0; i<N; i++)
{
printf("%4d ",data[i]);
}

printf("\ncomp ... %d times \n",comparison);
comp_sum += comparison;
loop++;
}
comp_ave = comp_sum / T;
printf("%d回平均 ... %.2f times\n",T,comp_ave);
}

int d_calc(void)
{
int i;
int t; /* int型なので小数点以下は必然的に切り捨て */

t = log10(N) / log10(2) - 1;
/* 対数の底の変換公式より */
d[t] = 1;
/* for(i=t; i>0; i--)
{
d[i-1] = 2*d[i]+1;
printf("%d %d\n",i,d[i]);
}
*/
return (t);
}

int shellsort(int t)
{
int j, n, p;
int i = 0, m;
int sp;
int insert;

for(j = t; j > 0; j--)
{
i = 0;
while(i < d[j])
{
sp = i;
m = 0;
while((d[j]*m+i) < N)
{
insert = data[d[j]*m+i];
for(n=i; n<=sp; n=n+d[j])
{
comparison++;
if(data[d[j] * m + i] < data[n])
{
for(p = sp; p>=n; p=p-d[j])
{
data[p+d[j]] = data[p];
}
data[n] = insert;
sp = d[j]*m+i;
break;
}
if(data[d[j]*m+i] > data[n] && n==sp)
{
sp = d[j]*m+i;
break;
}
}
m++;
}
i++;
}
}
}


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:アルゴリズム(シェルソート) 4364 まきじ 2005/07/22 23:42:37


No.4364

Re:アルゴリズム(シェルソート)
投稿者---まきじ(2005/07/22 23:42:37)


>文章にしていただけないでしょうか。

「文章」って何ですか?
コメントのことでしょうか?

>シェルソートのプログラムを何とか書きました。

自分でコーディングしたのなら、コメントぐらい付けれるでしょう。

#たぶん、誰もやってくれませんよ。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity