これだとさすがのコンピュータも処理に時間がかかってしまいます。
そこで、第５話の方法の改良を考えたいと思います。
最初にデータを大まかに5分類してから並び替えをするようにさせたいと思います。
まず、最大値と最小値を求めます。
次に、最大値と最小値の差を求めそれを4で割ったものを幅としてそれで分類するのです。
データ数が10個で
41 67 34 0 69 24 78 58 62 64
である場合を例に説明すると、
最大値が78、最小値が0ですから、
（最大値−最小値）÷4＝19.5です。
これを使って次のように分類します。
第1群 78以下で58.5より大きい場合 該当は67,69,78,62,64
第2群 58.5以下で39より大きい場合 該当は41,58
第3群 39以下で19.5より大きい場合 該当は34,24
第4群 19.5以下で0以上の場合 該当は0
最初の分類でデータは
67 69 78 62 64 41 58 34 24 0
となります。
これで前回の並び替え
void Nb(int* p,int n){
char 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)break;
}
String^ v=L"";
for(i=0;i<n;i++) v+=(p[i]).ToString()+L" ";
textBox8->Text=v;
}
を適用すると、3回のループで終わります。
分類を行わず41 67 34 0 69 24 78 58 62 64 のままで並び替えに掛けると、10回のループになります。
明らかに4分類してから、並び替えをした方が効率がいいことが分かります。
さらに、データ数が大きい場合の実験結果も示しておきましょう
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 の場合は、
分類しないで並び替えると２９ループであるのにたいして７ループです。計算回数は３０×２９=870回に対して、
分類する場合は分類に要した計算回数も含めて計算して３０×（７＋４）＝330回で、計算回数は約３７％で済んでいます。
また、47 26 71 38 69 12 67 99 35 94 3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 の場合は、
ループ数は２８VS５となり、計算回数は８４０回VS２７０回で、約3分の1です。
データ数が多いほど、分類した方が有利になります。
例えば、データ数１００の
33 15 39 58 4 30 77 6 73 86 21 45 24 72 70 29 77 73 97 12 86 90 61 36 55 67 55 74 31 52 50 50 41 24 66 30 7 91 7 37 57 87 53 83 45 9 9 58 21 88 22 46 6 30 13 68 0 91 62 55 10 59 24 37 48 83 95 41 2 50 91 36 74 20 96 21 48 99 68 84 81 34 53 99 18 38 0 88 27 67 28 93 48 83 7 21 10 17 13 14
の場合、ループ数は８７VS２２で、計算回数は8700回VS2600回となり、約3.3分の１となります。節約回数は、6100回にも及びます。
プログラム例を示して第６話は閉めたいと思います。
まず、フォームは次のようになっています。
そして、コードは下記の通りです。
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
int a[N];
int n=int::Parse(textBox1->Text);
ds(a,n);
if(n>9)Br(a,n);
Nb(a,n);
}
void Br(int* p,int n){
char 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];
}
textBox3->Text=max.ToString();
textBox4->Text=min.ToString();
double hb;
hb=((double)max-(double)min)/(double)4;
char a[4][N];
char cn[4];
for(i=0;i<4;i++){
cn[i]=0;
for(j=0;j<n;j++){
if(i<3){
if(p[j]>max-(i+1)*hb && p[j]<=max-i*hb){
a[i][cn[i]]=p[j];
cn[i]++;
}
if(i==3){
if(p[j]>=max-(i+1)*hb && p[j]<=max-i*hb){
a[i][cn[i]]=p[j];
cn[i]++;
}
}
}
}
char 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){
char 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){
textBox6->Text=(i+1).ToString();
break;
}
}
String^ v=L"";
for(i=0;i<n;i++) v+=(p[i]).ToString()+L" ";
textBox5->Text=v;
}
void ds(int* p,int n){
int i;
String^ w=L"";
for(i=0;i<n;i++){
p[i]=rand() % 100;
w+=(p[i]).ToString()+L" ";
}
textBox2->Text=w;
}
（コピーペースト用
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
int a[N];
int n=int::Parse(textBox1->Text);
ds(a,n);
if(n>9)Br(a,n);
Nb(a,n);
}
void Br(int* p,int n){
char 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];
}
textBox3->Text=max.ToString();
textBox4->Text=min.ToString();
double hb;
hb=((double)max-(double)min)/(double)4;
char a[4][N];
char cn[4];
for(i=0;i<4;i++){
cn[i]=0;
if(i<3){
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]++;
}
}
}
if(i==3){
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]++;
}
}
}
}
char ks=0;
if(cn[i]>0){
for(i=0;i<4;i++){
for(j=0;j<cn[i];j++){
p[ks]=a[i][j];
ks++;
}
}
}
}
void Nb(int* p,int n){
char 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){
textBox6->Text=(i+1).ToString();
break;
}
}
String^ v=L"";
for(i=0;i<n;i++) v+=(p[i]).ToString()+L" ";
textBox5->Text=v;
}
void ds(int* p,int n){
int i;
String^ w=L"";
for(i=0;i<n;i++){
p[i]=rand() % 100;
w+=(p[i]).ToString()+L" ";
}
textBox2->Text=w;
}
