第16講 データの並び換えに挑戦！
第７話 隣項交換繰り返し法を加える
実行画面
10 18 17 13 3 16 17 3 3 15
データの最小値は18です。
データの最大値は0です。
小さい順に並び換え
3 3 3 17 13 10 16 17 18 15
大きい順に並び換え
18 17 17 16 15 13 10 3 3 3
基データの再表示
10 18 17 13 3 16 17 3 3 15
隣項交換繰り返し法による昇順並べ直し
3 3 3 10 13 15 16 17 17 18
隣項交換繰り返し法による降順並べ直し
18 17 17 16 15 13 10 3 3 3
プロジェクト終了
を実現するプログラム例
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void f(int a[10]); //１桁のランダムデータを発生させる社員
char g(int a[10],int n); //データの１番小さい値を見つける社員
void h(int a[10]); //データ表示させる社員
char x(int a[10],int n); //データの1番大きい値を見つける社員
void j(int a[10]); //xを利用してデータを小さい順に並べ直す社員
void k(int a[10]); //gを利用してデータを大きい順に並べ直す社員
void cp(int a[10],int b[10]); //データのコピーを行う社員 aをbにコピー
void rs(int a[10]); //隣項交換繰り返し法による昇順並び換えを行う社員
void rk(int a[10]); //隣項交換繰り返し法による降順並び換えを行う社員
int main(){
int a[10],b[10],c[10],w;
srand((unsigned) time(NULL));
f(a); //１桁のランダムデータを発生させる社員
cp(a,b);
cp(a,c);
h(a);
w=g(a,0); //データの１番小さい値を見つける社員
printf("データの最小値は%dです。\n",a[w]);
w=x(a,10);
printf("データの最大値は%dです。\n",a[w]);
j(b); //xを利用してデータを小さい順に並べ直す社員
printf("小さい順に並び換え\n");
h(b);
k(c); //gを利用してデータを大きい順に並べ直す社員
printf("大きい順に並び換え\n");
h(c);
cp(a,b); //データの復元
cp(a,c); //データの復元
printf("基データの再表示\n");
h(a); //基データの表示
printf("隣項交換繰り返し法による昇順並べ直し\n");
rs(b); //隣項交換繰り返し法により、bを昇順に並べ直す。
h(b);
printf("隣項交換繰り返し法による降順並べ直し\n");
rk(c); //隣項交換繰り返し法により、cを降順に並べ直す。
h(c);
printf("プロジェクト終了\n");
}
void f(int a[10]){ //１桁のランダムデータを発生させる社員
int i;
for(i=0;i<10;i++){
a[i]=rand()%20;
}
}
void cp(int a[10],int b[10]){
int i;
for(i=0;i<10;i++){
b[i]=a[i];
}
}
char g(int a[10],int n){ //データの１番小さい値を見つける社員
int i,ik,mn;
mn=0;
for(i=n;i<10;i++){
if(mn<a[i]){
mn=a[i];
ik=i;
}
}
return(ik);
}
void h(int a[10]){ //データ表示させる社員
int i;
for(i=0;i<10;i++){
printf("%d ",a[i]);
}
printf("\n");
}
char x(int a[10],int n){ //データの1番大きい値を見つける社員
int i,ik,mx;
mx=10;
for(i=n;i<10;i++){
if(mx>a[i]){
mx=a[i];
ik=i;
}
}
return(ik);
}
void j(int a[10]){ //xを利用してデータを小さい順に並べ直す社員
int i,j,w;
for(i=0;i<9;i++){
j=x(a,i); //xはデータの１番小さい値を見つける社員
w=a[i];
a[i]=a[j];
a[j]=w;
}
}
void k(int a[10]){ //gを利用してデータを大きい順に並べ直す社員
int i,j,w;
for(i=0;i<9;i++){
j=g(a,i); //gはデータの１番大きい値を見つける社員
w=a[i];
a[i]=a[j];
a[j]=w;
}
}
void rs(int p[10]){ //隣項交換繰り返し法による昇順並び換えを行う社員
int i,j,cn,w;
for(i=0;i<10;i++){
cn=0;
for(j=0;j<9;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[10]){ //隣項交換繰り返し法による降順並び換えを行う社員
int i,j,cn,w;
for(i=0;i<10;i++){
cn=0;
for(j=0;j<9;j++){
if(p[j]<p[j+1]){
w=p[j];
p[j]=p[j+1];
p[j+1]=w;
cn++;
}
}
if(cn==0)return;
}
}
隣項交換繰り返し法を付け加えたプログラム
まだ、２つ研究課題が残っています。
第１は、
『最小値（最大値）排除繰り返し法』と『隣項交換繰り返し法』
のどちらが速く並び換えの成功するのか、
を明らかにすることです。
第２は、
隣項交換繰り返し法によって、
本当にｎ個のデータはｎ回以下の隣項交換繰り返し法によって、
交換できる
(佐藤予想、もちろん証明されているでしょうから、
この名称は正しくはないですが・・・）
かを明らかにすることです。
データが10項程度では、
0 1 12 0 16 5 9 0 14 10
データの最小値は16です。
データの最大値は0です。
小さい順に並び換え
0 0 0 1 5 9 14 16 12 10
並び換えに0.000000秒かかりました。大きい順に並び換え
16 14 12 10 9 5 1 0 0 0
並び換えに0.000000秒かかりました。基データの再表示
0 1 12 0 16 5 9 0 14 10
隣項交換繰り返し法による昇順並べ直し
0 0 0 1 5 9 10 12 14 16
並び換えに0.000000秒かかりました。隣項交換繰り返し法による降順並べ直し
16 14 12 10 9 5 1 0 0 0
並び換えに0.000000秒かかりました。
プロジェクト終了
のように時間を計測しても差は出ませんから、
データ数を５千から１万の任意の数を、
とることにして、
桁数も４桁以内にすることにしましょう。
また、佐藤予想は証明されていませんから、
void rs(int p[10]){ //隣項交換繰り返し法による昇順並び換えを行う社員
int i,j,cn,w;
for(i=0;i<10;i++){
cn=0;
for(j=0;j<9;j++){
if(p[j]>p[j+1]){
w=p[j];
p[j]=p[j+1];
p[j+1]=w;
cn++;
}
}
if(cn==0)return;
}
}
などの１次元目はwhile文に変更しておきましょう。
もちろん、総回数を数えるカウンタも必要になります。
さらに、データの個数（ksとします）は、
記述が煩雑になりますから、
グローバル変数としましょう。
グローバル変数は、
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
・
void rk(int a[10]); //隣項交換繰り返し法による降順並び換えを行う社員
int ks; //データ個数
int main(){
・
第10講の魔方陣自動生成で学んだ通りに、
mainの前に宣言する変数で、
有効範囲は、
プログラム全体です。
いわばグローバル変数は、
社長でも、社員でも共通に使える箱です。
それに対して、関数内でしか使えない箱を
ローカル変数といいます。
基本的には、グローバル変数は使わない方が、
良いとされていますが、
記述を簡単にするために数個程度なら使っても良いと思います。
これをmain内のローカル変数とすると、
すべての関数に引数で渡さなければなりませんから、
コードが複雑になってしまいます。
初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc++ c言語 c++ 入門 初心者 基礎から応用まで
eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ
