第１２講 様々な並び替えの方法
第10話 分類法と最大値最小値排除法の比較ソフト

今回は第7話の宿題に答えることにしましょう。
最大値と最小値を排除していく方法と分類法ではどちらが優れているか、調べてみましょう。
そこで、先のフォームを次のように改造し

コードソースを次のように変更します。
#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();

　　　　　　　　　　srand(static_cast<unsigned int>(0));
　　　　　　　　　　hj=DateTime::Now;
　　　　　　　　　　rk=0;
　　　　　　　　　　int ikn,ikx,j,k,w;
　　　　　　　　　　for(i=0;i<1000;i++){
　　　　　　　　　　　　ds(a,n);
　　　　　　　　　　　　for(j=0;j<(n/2);j++){
　　　　　　　　　　　　　　for(k=j;k<n-j;k++){
　　　　　　　　　　　　　　　　ikn=Mn(a,j,n);
　　　　　　　　　　　　　　　　w=a[n-1-j];
　　　　　　　　　　　　　　　　a[n-1-j]=a[ikn];
　　　　　　　　　　　　　　　　a[ikn]=w;
　　　　　　　　　　　　　　　　ikx=Mx(a,j,n);
　　　　　　　　　　　　　　　　w=a[j];
　　　　　　　　　　　　　　　　a[j]=a[ikx];
　　　　　　　　　　　　　　　　a[ikx]=w;
　　　　　　　　　　　　　　}
　　　　　　　　　　　}
　　　　　　　　　　　hy(a,n);
　　　　　　　　　}
　　　　　　　　　ow=DateTime::Now;
　　　　　　　　　sa=ow->Subtract(*hj);
　　　　　　　　　textBox8->Text=(sa.TotalSeconds).ToString();
　　　　　　　}

　　　　　　　void hy(int* p,int n){
　　　　　　　　　int i;
　　　　　　　　　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";
　　　　　　　　　}
　　　　　　　　　label13->Text=v;
　　　　　　　}

　　　　　　　int Mx(int* p,int m,int n){
　　　　　　　　　int i,ik;
　　　　　　　　　int Max=0;
　　　　　　　　　for(i=m;i<n-m;i++){
　　　　　　　　　　　if(p[i]>Max){
　　　　　　　　　　　　　Max=p[i];
　　　　　　　　　　　　　ik=i;
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　　　return(ik);
　　　　　　　}
　　　　　　　int Mn(int* p,int m,int n){
　　　　　　　　　int i,ik;
　　　　　　　　　int Min=1000000;
　　　　　　　　　for(i=m;i<n-m;i++){
　　　　　　　　　　　if(p[i]<Min){
　　　　　　　　　　　Min=p[i];
　　　　　　　　　　　ik=i;
　　　　　　　　　}
　　　　　　　}
　　　　　　　return(ik);
　　　　　}
以下同じ。
（コピーペースト用

#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();

srand(static_cast<unsigned int>(0));
hj=DateTime::Now;
rk=0;
int ikn,ikx,j,k,w;
for(i=0;i<1000;i++){
ds(a,n);
for(j=0;j<(n/2);j++){
for(k=j;k<n-j;k++){
ikn=Mn(a,j,n);
w=a[n-1-j];
a[n-1-j]=a[ikn];
a[ikn]=w;
ikx=Mx(a,j,n);
w=a[j];
a[j]=a[ikx];
a[ikx]=w;
}
}
hy(a,n);
}
ow=DateTime::Now;
sa=ow->Subtract(*hj);
textBox8->Text=(sa.TotalSeconds).ToString();
}

void hy(int* p,int n){
int i;
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";
}
label13->Text=v;
}

int Mx(int* p,int m,int n){
int i,ik;
int Max=0;
for(i=m;i<n-m;i++){
if(p[i]>Max){
Max=p[i];
ik=i;
}
}

return(ik);
}

int Mn(int* p,int m,int n){
int i,ik;
int Min=1000000;
for(i=m;i<n-m;i++){
if(p[i]<Min){
Min=p[i];
ik=i;
}
}
return(ik);
}




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+1;i++){
cn[i]=0;
for(j=0;j<n;j++){
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+1;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;
}

）

srand(static_cast<unsigned int>(0));はrand()を初期化するものです。
これを入れとおくと、分類法で作成するデータと最大値最小値排除法で作成されるデータがまったく同一のものになります。
（1000回のトータル時間（1000で割れば平均時間）で比較しているので、初期化はしなくてもよいことはよいのですが、
完全に同一のデータで比較するため今回srand(static_cast<unsigned int>(0));を入れました。例えば、srand(static_cast<unsigned int>(0));を
srand(static_cast<unsigned int>(time(0)));と変更すると時間ごとの異なる乱数系列を与えることができます。
後で数独問題作成ソフトに挑戦することになりますが、
srand(static_cast<unsigned int>(time(0)));がないと、
1回目に起動したときに最初に作る問題と、
2回目に起動したときに最初に作る問題がまったく同じものになってしまいます。
起動中の1回1回は違う問題を作るにしても、起動後は同じ順番で問題を作成してしまいます。
乱数系列の指定がないと、コンピュータは毎回同じパターンで乱数を発生させるからです。
乱数の発生のパターンを変更するためには、異なる乱数系列を指定しなければなりません。
連数系列の指定は、srand(static_cast<unsigned int>(整数値))で行います。
これは、乱数系列の指定であると同時に初期化でもあります。
例えば、次のようにコーティングすると、
int i;
String^ w;
srand(static_cast<unsigned int>(0));
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
w+=L"\n";
srand(static_cast<unsigned int>(0));
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
label1->Text=w;

label1には次のように表示されます。

それに対して、srand(static_cast<unsigned int>(0));がないコーティング
int i;
String^ w;
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
w+=L"\n";
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
label1->Text=w;
では実行結果は、
となります。
srand(static_cast<unsigned int>(0));は乱数系列の指定であると同時に初期化であることが分かります。
また、コーティングを次のように変更すると
int i;
String^ w;
srand(static_cast<unsigned int>(1));
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
w+=L"\n";
srand(static_cast<unsigned int>(1));
for(i=0;i<5;i++){
　　w+=(rand()).ToString()+L" ";
}
label1->Text=w;

となり、異なる乱数系列であることが分かります。



注　ある親切な読者からコードの間違いが指摘されました。
　　　　　　　　　　for(i=0;i<1000;i++){
　　　　　　　　　　　　ds(a,n);
　　　　　　　　　　　　for(j=0;j<(n/2);j++){
　　　　　　　　　　　　　　for(k=j;k<n-j;k++){
　　　　　　　　　　　　　　　　ikn=Mn(a,j,n);
　　　　　　　　　　　　　　　　w=a[n-1-j];
　　　　　　　　　　　　　　　　a[n-1-j]=a[ikn];
　　　　　　　　　　　　　　　　a[ikn]=w;
　　　　　　　　　　　　　　　　ikx=Mx(a,j,n);
　　　　　　　　　　　　　　　　w=a[j];
　　　　　　　　　　　　　　　　a[j]=a[ikx];
　　　　　　　　　　　　　　　　a[ikx]=w;
　　　　　　　　　　　　　　}
　　　　　　　　　　　}
のfor(k=j;k<n-j;k++){・・・}は意味がないというご指摘です。
ご指摘の通り、kはどこにも使われていませんから、
同じ処理を何回も繰り返していることになります。
ですから、
コードは次のように変更すべきということになります。
　　　　　　　　　　for(i=0;i<1000;i++){
　　　　　　　　　　　　ds(a,n);
　　　　　　　　　　　　for(j=0;j<(n/2);j++){
　　　　　　　　　　　　　　ikn=Mn(a,j,n);
　　　　　　　　　　　　　　w=a[n-1-j];
　　　　　　　　　　　　　　a[n-1-j]=a[ikn];
　　　　　　　　　　　　　　a[ikn]=w;
　　　　　　　　　　　　　　ikx=Mx(a,j,n);
　　　　　　　　　　　　　　w=a[j];
　　　　　　　　　　　　　　a[j]=a[ikx];
　　　　　　　　　　　　　　a[ikx]=w;
　　　　　　　　　　　}
間違いによって、読者の皆様を混乱に陥れたことについて、
心よりお詫び申し上げます。
そして、間違いを指摘してくださった読者に感謝申し上げます。
コードを訂正すると最大値・最小値排除法の方が分類法より１５％程速くなります。





第5話で予告したとおり、この第12講の最後でライブラリにあるsetとsortを利用する方法を紹介することになっています。
setとsortを利用を利用すれば、より迅速にできるでしょうが、大事なことは自分で考えることです。
理由は、ここで考えたことは必ず他で応用できるからです。
setとsortを利用することは既製品を利用するのと同じです。
それに対して、自分で作るのはオーダーメートすることに相当します。
プログラミングにおいて大事なのは、アイデアです。
是非、皆さん考えてみてください。

第１２講第９話へ　第１２講第11話へ



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