第16講 データの並び換えに挑戦!

第8話 両方法のどちらが速い?佐藤仮説は正しい?
第7話の2つの問題を検証するプログラム例
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void f(int a[20000]); //1桁のランダムデータを発生させる社員
char g(int a[20000],int n); //データの1番小さい値を見つける社員
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); //1桁のランダムデータを発生させる社員
  cp(a,b);
  cp(a,c);
  h(a);
  w=g(a,0); //データの1番小さい値を見つける社員
  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]){ //1桁のランダムデータを発生させる社員
  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){ //データの1番小さい値を見つける社員
  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はデータの1番小さい値を見つける社員
    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はデータの1番大きい値を見つける社員
    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;
  }
}

2つの問題を検証するプログラム

実行結果
         ・
データの最小値は9999です。
データの最大値は9170です。
小さい順に並び換え
並び換えにかかった時間は0.005000秒です。
         ・
大きい順に並び換え
並び換えにかかった時間は0.005000秒です。
         ・
隣項交換繰り返し法による昇順並べ直し
並び換えにかかった時間は0.015000秒です。
         ・
佐藤仮説は正しい。
隣項交換繰り返し法による昇順並べ直し
並び換えにかかった時間は0.015000秒です。
         ・
佐藤仮説は正しい。
プロジェクト終了


あれっ?
私の記憶では、
隣項交換繰り返し法が圧勝するはずだったのですが、
逆になってしまいました。
でも、今読み返してみたら、
vba 2016 入門講義にも同じことが書いてありますから、
完全な記憶違いでしょうか。
でも、佐藤仮説は正しそうですね。
おそらく何回やっても正しいと出てくるでしょう。

第17講では、10進法をn進法に変換するソフトを作ります。

第7話へ 第17講第1話へ

a


初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc++ c言語 c++ 入門 初心者 基礎から応用まで
eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門

数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座

初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ