第６話 最小値排除繰り返し法自己再帰版
コード例
#include<iostream>
#include<ctime>
#include<stdlib.h>
using namespace std;
using namespace System;
void f(int a,int *m);
void g(int a,int *m);
void h(int x,int a,int *m);
int main(){
srand(static_cast<unsigned int>(time(0)));
int n,*m;
m=(int *)malloc(2000000);
cout<<"発生させるデータ数をキーボードから入力してください。"<<endl<<"データ数＝";
scanf("%d",&n);
f(n,m);
DateTime^ hj=DateTime::Now; //開始時間
g(n,m);
DateTime^ ow=DateTime::Now; //終了時間
TimeSpan sa=ow->Subtract(*hj); //経過時間の計算
cout<<"並び替え時間は"<<sa.TotalSeconds<<"秒です。"<<endl;
}
void f(int a,int *m){
int i;
i=0;
while(i<a){
m[i]=rand()%100;
if(m[i]<10)cout<<" "<<m[i]<<" ";
if(m[i]>=10)cout<<m[i]<<" ";
if(i>0 && (i+1)%25==0)cout<<endl;
i++;
}
cout<<endl;
}
void g(int a,int *m){
int i;
h(0,a,m);
cout<<"並び替え後"<<endl;
i=0;
while(i<a){
if(m[i]<10)cout<<" "<<m[i]<<" ";
if(m[i]>=10)cout<<m[i]<<" ";
if(i>0 && (i+1)%25==0)cout<<endl;
i++;
}
cout<<endl;
}
void h(int x,int a,int *m){
int i,min,ik,w;
min=10000;
for(i=x;i<a;i++){
if(m[i]<min){
min=m[i];
ik=i;
}
}
w=m[x];
m[x]=m[ik];
m[ik]=w;
if(x+1<a-1)h(x+1,a,m);
}
変更の場所はピンクのところのみです。
ですから、たったの３カ所です。
降順も昇順も本質的には変わりありません。
今まで降順ばかり説明してきましたが、
降順を代表例に選んだにすぎません。
もちろん、昇順すなわち最小値排除繰り返し法を代表に選んでもよかった訳です。
さて、前話で予告しました。
隣項交換繰り返し法と最大値（最小値）排除繰り返し法のマルチスレッド化に挑戦します。
隣項交換繰り返し法はどのようにしたらマルチスレッド化できますか。
そして、最大値（最小値）排除繰り返し法についてはマルチ化は可能でしょうか。
また、それぞれのマルチ化によってどれぐらいスピードアップするのでしょうか。
第５話へ 第２３講第１話へ
