第１２講 様々な並び替えの方法
第７話 並び替え第３の方法の改良の試み

第６話においては、データ数が３０までで、範囲が０から１００までの整数に限られ、分類数も４と固定されていました。
ここではより大量のデータを扱えるようにして、範囲も分類数も任意に変更できるようにして、
前回のプログラムをより高速化できるか実験してみましょう。
まず、フォームは次のように改造します。

そして、ソースコードは、

　　　　　・
　　　　　・
　　　　　・



（コピーペースト用
#include<stdlib.h>
const int N=300;
int rk=0;



#pragma endregion
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
int a[N];
int n=int::Parse(textBox1->Text);
int i;
srand(static_cast<unsigned int>(0));
DateTime^ hj=DateTime::Now;
rk=0;
for(i=0;i<1000;i++){
ds(a,n);
if(n>9)Br(a,n);
Nb(a,n);
}
textBox6->Text=((double)rk/(double)1000).ToString();
DateTime^ ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
textBox7->Text=(sa.TotalSeconds).ToString();
}
void Br(int* p,int n){
int i,j;
int w=0;
int max=0,min=100;
for(i=0;i<n;i++){
if(max<p[i])max=p[i];
if(min>p[i])min=p[i];
}
textBox4->Text=max.ToString();
textBox5->Text=min.ToString();
double hb;
int M;
M=int::Parse(textBox3->Text);
hb=((double)max-(double)min)/(double)M;
int a[100][N];
int cn[100];
for(i=0;i<M;i++){
cn[i]=0;
for(j=0;j<n;j++){
if(i<M-1){
if(p[j]>max-(i+1)*hb && p[j]<=max-i*hb){
a[i][cn[i]]=p[j];
cn[i]++;
}
}
if(i==M-1){
if(p[j]>=max-(i+1)*hb && p[j]<=max-i*hb){
a[i][cn[i]]=p[j];
cn[i]++;
}
}
}
}
int ks=0;
for(i=0;i<M;i++){
if(cn[i]>0){
for(j=0;j<cn[i];j++){
p[ks]=a[i][j];
ks++;
}
}
}
}
void Nb(int* p,int n){
int i,j;
int w,cn;
for(i=0;i<n-1;i++){
cn=0;
for(j=0;j<n-1;j++){
if(p[j]<p[j+1]){
w=p[j];
p[j]=p[j+1];
p[j+1]=w;
cn++;
}
}
if(cn==0){

rk+=i+1;
break;
}
}
String^ v=L"";
for(i=0;i<n;i++){
if(p[i]<10){
v+=L"00"+(p[i]).ToString()+L" ";
}
else if(p[i]<100){
v+=L"0"+(p[i]).ToString()+L" ";
}
else{
v+=(p[i]).ToString()+L" ";
}
if(i>0 && (i+1)%40==0)v+=L"\n";
}
label9->Text=v;
}
void ds(int* p,int n){
int i;
String^ w=L"";
int s;
s=int::Parse(textBox2->Text);
for(i=0;i<n;i++){
p[i]=rand() % s;
if(p[i]<10){
w+=L"00"+(p[i]).ToString()+L" ";
}
else if(p[i]<100){
w+=L"0"+(p[i]).ToString()+L" ";
}
else{
w+=(p[i]).ToString()+L" ";
}
if(i>0 && (i+1)%40==0)w+=L"\n";
}
label5->Text=w;
}

）

このソフトによって、最適状態は見つけられるでしょうか。
そして、大幅な改善は見られるでしょうか。

ところが、実験結果は思わしくありません。

データ数３００，範囲１００の場合（計測時間は、１０００回トータル計測時間）

データ数３００，範囲１０００の場合（計測時間は、１０００回トータル計測時間）

期待通り平均ループ回数は、データ数３００，範囲1000の場合10分の1以下など大幅に改善されましたが、
計算速度の方は、範囲１００の場合最大効果でも１１６％、
範囲１０００においては、最大で最大効果１１３％にすぎません。
どうやら分類法は、たいした改善にはならないようです。
ループ回数が大幅に改善されても、分類に時間が食われてしまい、
結果は相殺されてしまうようです。

では、より高速化するにはどのような工夫が考えられるでしょうか。
皆さんも考えてみてください。

さらに、皆さんに、問題を出しましょう。今までで大きく分けて３つの並び替えの方法を考えました。
２番目と３番目の比較は、今日の実験でできましたが、
１番目と２番目ではどちらが優れているか実験してはいません。
皆さん、第７話のプログラムを改善して、どちらが優れているか実験で確かめましょう。

第６話と第７話のソースコードの詳しい解説は、次話で行いますが、１つだけ解説しておきましょう。。

DateTime^ hj=DateTime::Now;
for(i=0;i<1000;i++){
　　ds(a,n);
　　if(n>9)Br(a,n);
　　Nb(a,n);
}
DateTime^ ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
textBox7->Text=(sa.TotalSeconds).ToString();

ピンクの部分は、時間計測のために必要なものです。
DateTime^ hj=DateTime::Now;においてDateTime^型の変数hjを宣言し、
現在の時間の代入も行っています。
C言語の特徴で、宣言と初期化（最初の値を代入すること）同時に行えるのです。
つまり、DateTime^ hj=DateTime::Now;は
DateTime^ hj;
hj=DateTime::Now;
と同じです。私は、このように略した書き方は好みませんので、いつもは２行に分けています。
int i;
for(i=0;i<100;i++){
　　　・
　　　・
は
for(int i=0;i<100;i++){
　　　・
　　　・
と略することもできます。
また、DateTime::Nowで現在の時間を取得できます。
DateTime^ ow=DateTime::Now;も現在の時間（つまり終わりの時間）を取得しています。
TimeSpan sa=ow->Subtract(*hj);はTimeSpan型の時間の差変数saを宣言し、
hjとowの差つまり初めと終わりの時間差を求めています。
宣言を
DateTime hj=DateTime::Now;
DateTime ow=DateTime::Now;
（ハンドルマーク＾がない）
でしておけば、ここの式はもっとシンプルな
TimeSpan sa=ow-hj;になります。
^付で宣言すると、owとhjの差を求める計算はow->Subtract(*hj)のようになるのです。
これは、決まりだと思ってください。この書き方が気にいらない方は、ハンドル＾を入れないで宣言しましょう。
sa.TotalSecondsの.TotalSecondsは時間差を秒単位にするためのものです。

第１１講第６話へ　第１２講第６話へ　第１２講第８話へ　第１３講第１話へ

vc++講義第1部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座へ