第16講 データの並び換えに挑戦！
第８話 両方法のどちらが速い？佐藤仮説は正しい？
第７話の２つの問題を検証するプログラム例
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void f(int a[20000]); //１桁のランダムデータを発生させる社員
char g(int a[20000],int n); //データの１番小さい値を見つける社員
void h(int a[20000]); //データ表示させる社員
char x(int a[20000],int n); //データの1番大きい値を見つける社員
void j(int a[20000]); //xを利用してデータを小さい順に並べ直す社員
void k(int a[20000]); //gを利用してデータを大きい順に並べ直す社員
void cp(int a[20000],int b[20000]); //データのコピーを行う社員 aをbにコピー
void rs(int a[20000]); //隣項交換繰り返し法による昇順並び換えを行う社員
void rk(int a[20000]); //隣項交換繰り返し法による降順並び換えを行う社員
int ks;//データ個数
int main(){
int a[20000],b[20000],c[20000],w;
clock_t hj,ow;
srand((unsigned) time(NULL));
ks=1000+rand()%1000;
f(a); //１桁のランダムデータを発生させる社員
cp(a,b);
cp(a,c);
h(a);
w=g(a,0); //データの１番小さい値を見つける社員
printf("データの最小値は%dです。\n",a[w]);
w=x(a,ks);
printf("データの最大値は%dです。\n",a[w]);
hj=clock();
j(b); //xを利用してデータを小さい順に並べ直す社員
ow=clock();
printf("小さい順に並び換え\n");
h(b);
printf("並び換えにかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
hj=clock();
k(c); //gを利用してデータを大きい順に並べ直す社員
ow=clock();
printf("大きい順に並び換え\n");
h(c);
printf("並び換えにかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
cp(a,b); //データの復元
cp(a,c); //データの復元
printf("基データの再表示\n");
h(a); //基データの表示
printf("隣項交換繰り返し法による昇順並べ直し\n");
hj=clock();
rs(b); //隣項交換繰り返し法により、bを昇順に並べ直す。
ow=clock();
h(b);
printf("並び換えにかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
printf("隣項交換繰り返し法による降順並べ直し\n");
hj=clock();
rk(c); //隣項交換繰り返し法により、cを降順に並べ直す。
ow=clock();
h(c);
printf("並び換えにかかった時間は%f秒です。\n",(double)(ow - hj) / CLOCKS_PER_SEC);
printf("プロジェクト終了\n");
}
void f(int a[20000]){ //１桁のランダムデータを発生させる社員
int i;
for(i=0;i<ks;i++){
a[i]=rand()%10000;
}
}
void cp(int a[20000],int b[20000]){
int i;
for(i=0;i<ks;i++){
b[i]=a[i];
}
}
char g(int a[20000],int n){ //データの１番小さい値を見つける社員
int i,ik,mn;
mn=0;
for(i=n;i<ks;i++){
if(mn<a[i]){
mn=a[i];
ik=i;
}
}
return(ik);
}
void h(int a[20000]){ //データ表示させる社員
int i;
for(i=0;i<ks;i++){
printf("%d ",a[i]);
if(i>0 && i%50==0)printf("\n");
}
printf("\n");
}
char x(int a[20000],int n){ //データの1番大きい値を見つける社員
int i,ik,mx;
mx=ks;
for(i=n;i<ks;i++){
if(mx>a[i]){
mx=a[i];
ik=i;
}
}
return(ik);
}
void j(int a[20000]){ //xを利用してデータを小さい順に並べ直す社員
int i,j,w;
for(i=0;i<ks-1;i++){
j=x(a,i); //xはデータの１番小さい値を見つける社員
w=a[i];
a[i]=a[j];
a[j]=w;
}
}
void k(int a[20000]){ //gを利用してデータを大きい順に並べ直す社員
int i,j,w;
for(i=0;i<ks-1;i++){
j=g(a,i); //gはデータの１番大きい値を見つける社員
w=a[i];
a[i]=a[j];
a[j]=w;
}
}
void rs(int p[20000]){ //隣項交換繰り返し法による昇順並び換えを行う社員
int i,j,cn,w;
for(i=0;i<ks;i++){
cn=0;
for(j=0;j<ks-1;j++){
if(p[j]>p[j+1]){
w=p[j];
p[j]=p[j+1];
p[j+1]=w;
cn++;
}
}
if(cn==0)return;
}
}
void rk(int p[20000]){ //隣項交換繰り返し法による降順並び換えを行う社員
int i,j,cn,w;
for(i=0;i<ks;i++){
cn=0;
for(j=0;j<ks-1;j++){
if(p[j]<p[j+1]){
w=p[j];
p[j]=p[j+1];
p[j+1]=w;
cn++;
}
}
if(cn==0)return;
}
}
２つの問題を検証するプログラム
実行結果
・
データの最小値は9999です。
データの最大値は9170です。
小さい順に並び換え
並び換えにかかった時間は0.005000秒です。
・
大きい順に並び換え
並び換えにかかった時間は0.005000秒です。
・
隣項交換繰り返し法による昇順並べ直し
並び換えにかかった時間は0.015000秒です。
・
佐藤仮説は正しい。
隣項交換繰り返し法による昇順並べ直し
並び換えにかかった時間は0.015000秒です。
・
佐藤仮説は正しい。
プロジェクト終了
あれっ？
私の記憶では、
隣項交換繰り返し法が圧勝するはずだったのですが、
逆になってしまいました。
でも、今読み返してみたら、
vba 2016 入門講義にも同じことが書いてありますから、
完全な記憶違いでしょうか。
でも、佐藤仮説は正しそうですね。
おそらく何回やっても正しいと出てくるでしょう。
第17講では、10進法をｎ進法に変換するソフトを作ります。
初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc++ c言語 c++ 入門 初心者 基礎から応用まで
eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ
