研究帖8

ナイス博士「BB君、ゲームの研究は進んでるかね？」

BB君「いや、全然だめです。」

ナイス博士「何だ。どうしたんだね？」

BB君「実は、ゲームよりもっと面白い研究をしたいんです。」

ナイス博士「何だ、気まぐれだな。何がやりたいんだね？」

BB君「僕はアルゴリズムに興味があるので、いろいろやりたいんです。」

ナイス博士「たとえば？」

BB君「例えばソートですね。普通、ソートは１つの配列内だけでやるでしょ？なぜですか？」

ナイス博士「知らないな。一種のゲームのルールのような物じゃないか？」

BB君「これを、好きなだけ配列や変数を使ってやってよければ、もっといろいろ出来るのではないでしょうか。」

ナイス博士「うーん、なるほどね。出来るかもしれないね。そういえば、君は以前、エクセルvbaで、勝ち点ソートと言うのを作ったね？」

BB君「ええ、あれは、それぞれの数を比較して、大きいほうに勝ち点を与えて、順番を決めるのですが、その改良版を作りました。これです！動かしてみて下さい。」

【プログラムMySort.java】**************************

import nice.*;

class MySort{
	public static void main(String args[]){
		
		int ii[]={1,-2,5,6,19,1,8,-4,11,1,-3,10};
		int ii2[]=new int[ii.length];
		
		ii2=new BSort().wSort3(ii);

		for(int i=0;i<ii2.length;i++){
			System.out.print(ii2[i]+",");
		}
	}
}

class BSort{
	
	int[] wSort3(int[] ii){
		
		int ii2[]=new int[ii.length];
		int iiw[]=new int[ii.length];
		
		for(int i=0;i<ii.length;i++){
			for(int j=i+1;j<ii.length;j++){
				if(ii[i]>ii[j])	iiw[i]+=1;
				if(ii[i]<ii[j])	iiw[j]+=1;
			}
			ii2[sa(iiw[i],ii2)]=ii[i];
		}

		return ii2;
	}
	

	int sa(int i,int[] ii2){
		if(ii2[i]==0)return i;
		return sa(i+1,ii2);
	}
		
	
}

ナイス博士「ほう、ちゃんと動くね。他と比べて早いのかい？」

BB君「分かりませんが、いろいろテストしたいと思います。」

ナイス博士「そうか。じゃ、やって見てくれ。」

...続く

BB君「博士、単純ソートと比較したんですが.........」

ナイス博士「うん、どうだったい？」

BB君「両方とも0/1000秒です。」

ナイス博士「へええ、早いな。コードを見せてくれ。」

BB君「これです。」

【プログラムSortStudy2.java】**************************

import nice.*;
import java.util.*;

class SortStudy2{
	public static void main(String args[]){
		
		int ii[]={1,-2,5,6,19,1,8,-4,11,1,-3,10,21,59,45,13,19,17,55,41,32,98,1,-2,
			5,6,19,1,8,-4,11,1,-3,10,21,59,45,13,19,17,55,41,32,98,1,32};

		System.out.println("要素数:"+ii.length);
		long startTime = System.currentTimeMillis();

		ii=new BSort().wSort3(ii);
		//new ManySort().SimpleSort(ii);
		
		long goalTime = System.currentTimeMillis();
		System.out.println("Time:"+(goalTime-startTime));

		for(int i=0;i<ii.length;i++){
			System.out.print(ii[i]+",");
		}
		
	}
}

class ManySort{
	int[] SimpleSort(int[] ii){
		int k;
		for(int i=0;i<ii.length-1;i++){
			for(int j=i+1;j<ii.length;j++){
				if(ii[i]>ii[j]){
					k=ii[j];
					ii[j]=ii[i];
					ii[i]=k;
				}
			}
		}
		return ii;
	}
}
				

class BSort{
	int[] wSort3(int[] ii){
		
		int ii2[]=new int[ii.length];
		int iiw[]=new int[ii.length];
		
		for(int i=0;i<ii.length;i++){
			for(int j=i+1;j<ii.length;j++){
				if(ii[i]>ii[j]) iiw[i]+=1;
				if(ii[i]<=ii[j]) iiw[j]+=1;　　　//変更部分
			}
			ii2[iiw[i]]=ii[i];
		}

		return ii2;
	}
}

ナイス博士「メソッドｓａがなくなったな。」

BB君「ｓａは、同じ数だとインデックスが同じになるので、ずらすために作ったんで すが、同点の時に後の勝ち点だけ増やすようにしたんで、いらなくなったんです。」

ナイス博士「うまい！単純だが合理的だな。ところで要素数が45では少なくて比較出来ないん じゃないか？1000ぐらい作ったら？」

BB君「そんな、要素が1000の配列なんて、簡単に出来ませんよ。」

ナイス博士「プログラムで作るんだ。たとえば、こうだよ。」

【プログラムSortStudy2.java】**************************

class ArrayMaker{                    //インデックスの最大値を与え、昇順､降順､ランダムなint型配列を作る。表示する。
	int[] dArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			ii[i]=imax-i;
		}
		
		return ii;
	}
	
	int[] aArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			ii[i]=i;
		}
		
		return ii;
	}
	
	int[] adArray(int imax){
		int[] ii=new int[imax+1];
		int j=0;
		for(int i=0;i<ii.length-1;i+=2){
			ii[i]=j;
			ii[i+1]=imax-j;
			j++;
		}
		
		return ii;
	}
	
	int[] rArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			double dr=Math.random()*imax;
			ii[i]=(int)dr;
		}
		
		return ii;
	}
	
	
	void arrayPrinter(int[] ii){             //配列を表示する。
		for(int i=0;i<ii.length;i++){
			System.out.print(ii[i]+",");
		}
	}
}

ナイス博士「これらのうちどれかのメソッドに、インデックスの最大値を引数として与えて動かすと、いろんな配列が出来るんだ。」

BB君「それでは、いろんなソートと比較して、速度を量って見ましょう。」

ナイス博士「待ってくれ。私もソートを作ったので入れてくれ。」

BB君「それでは、細かいところを直して、全部入れて書き直します。」

【プログラムSortStudy2.java】**************************

//import nice.*;
import java.util.*;

class SortStudy2{
	public static void main(String args[]){
		
		//int ii[]={1,-2,5,6,19,1,8,-4,11,1,-3,10,21,59,45,13,19,17,55,41,32,98,1,-2,5,6,19,1,8,-4,11,1,
		//	-3,10,21,59,45,13,19,17,55,41,32,98,1,32};     //サンプル手動作成
		 
		
		ArrayMaker ar=new  ArrayMaker();      //サンプル作成
		
		//int[] ii=ar.aArray(18000);              //昇順
		//int[] ii=ar.dArray(18000);              //降順
		int[] ii=ar.rArray(18000);              //ランダム
		//int[] ii=ar.adArray(18000);           	   //昇降
		
		ar.arrayPrinter(ii);                   //配列表示
		System.out.println("\n\nStart");

		long startTime = System.currentTimeMillis();  //*******************************スタート時間
		
		//Arrays.sort(ii);//ad16,d15,a16,r16

		//ii=new BBSort().wSort3(ii);            //d2375,a2406,ad2406-------かかった時間
		
		//new ManySort().SimpleSort(ii);         //d2297,a1203,ad1750
		//new ManySort().SimpleSort2(ii);        //d1203,a1000,ad1062
		//new ManySort().SimpleSort3(ii);        //d1187,a984,ad1047
		//new ManySort().SimpleSort3v2(ii);      //d1187,a984,ad1062
		new ManySort().bubbleSort(ii);           //d1812,a1000,ad1407,r2235
		
		//new NiceSort().SimpleSortSpeedy(ii);   //a688,r688,d891
		//ii=new NiceSort().indexSort(ii);       //d16,a16,ad1672,1625
		
		long goalTime = System.currentTimeMillis();    //*********************************ゴール時間

		ar.arrayPrinter(ii);
		System.out.println("\n\n要素数:"+ii.length);
		System.out.println("Time:"+(goalTime-startTime));  //                             時間計算
	}
	
	
}


class ArrayMaker{                    //インデックスの最大値を与え、昇順､降順､ランダムなint型配列を作る。表示する。
	int[] dArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			ii[i]=imax-i;
		}
		
		return ii;
	}
	
	int[] aArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			ii[i]=i;
		}
		
		return ii;
	}
	
	int[] adArray(int imax){
		int[] ii=new int[imax+1];
		int j=0;
		for(int i=0;i<ii.length-1;i+=2){
			ii[i]=j;
			ii[i+1]=imax-j;
			j++;
		}
		
		return ii;
	}
	
	int[] rArray(int imax){
		int[] ii=new int[imax+1];
		
		for(int i=0;i<ii.length;i++){
			double dr=Math.random()*imax;
			ii[i]=(int)dr;
		}
		
		return ii;
	}
	
	
	void arrayPrinter(int[] ii){             //配列を表示する。
		for(int i=0;i<ii.length;i++){
			System.out.print(ii[i]+",");
		}
	}
}
		


class ManySort{                             //選択ソート4種類
	int[] SimpleSort(int[] ii){
		int k;
		for(int i=0;i<ii.length-1;i++){
			for(int j=i+1;j<ii.length;j++){
				if(ii[i]>ii[j]){
					k=ii[j];
					ii[j]=ii[i];
					ii[i]=k;
				}
			}
		}
		return ii;
	}
	
	int[] SimpleSort2(int[] ii){
		int k,imin,index;
		for(int i=0;i<ii.length-1;i++){
			imin=ii[i];
			index=i;
			for(int j=i+1;j<ii.length;j++){
				if(imin>ii[j]){
					imin=ii[j];
					index=j;
				}
			}	
			k=ii[i];
			ii[i]=ii[index];
			ii[index]=k;
		}
		return ii;
	}
	
	
	int[] SimpleSort3(int[] ii){
		for(int i=0;i<ii.length-1;i++){
			int imin=ii[i],k=i;
			for(int j=i+1;j<ii.length;j++) if(ii[j]<imin){
				imin=ii[j];
				k=j;
			}
			ii[k]=ii[i];
			ii[i]=imin;
		}
		return ii;
	}
	
	int[] SimpleSort3v2(int[] ii){
		int imin,k;
		for(int i=0;i<ii.length-1;i++){
			imin=ii[i];
			k=i;
			for(int j=i+1;j<ii.length;j++)
				if(imin>ii[j]){
					imin=ii[j];
					k=j;
				}
				ii[k]=ii[i];
				ii[i]=imin;
			
		}
		return ii;
	}	
	
	
	int[] bubbleSort(int[] ii){
	
		for(int j=ii.length-1;j>0;j--){
			for(int k=0;k<j;k++){
				
				if(ii[k]>ii[k+1]){
					int l=ii[k+1];
					ii[k+1]=ii[k];
					ii[k]=l;
				}
				
			}
		}
		return ii;
		
	}
	
	
	
}
				


class BBSort{                                  //BB君が作ったソート
	int[] wSort3(int[] ii){
		
		int ii2[]=new int[ii.length];
		int iiw[]=new int[ii.length];
		
		for(int i=0;i<ii.length;i++){
			for(int j=i+1;j<ii.length;j++){
				if(ii[i]>ii[j]) iiw[i]+=1;
				if(ii[i]<=ii[j]) iiw[j]+=1;
			}
			ii2[iiw[i]]=ii[i];
		}

		return ii2;
	}
}


class NiceSort{                                //ナイス博士が作ったソート
	
	int[] indexSort(int[] ii){ 
		int[] ii2=new int[ii.length];
		int[] ii3=new int[ii.length];
			
		int maxp=0,minp=0;
		
		for(int i=1;i<ii.length;i++){
			if(ii[i]>=ii[maxp]){
				ii2[i]=ii2[maxp]+1;
				maxp=i;
			}
			else if(ii[i]<=ii[minp]){
				ii2[i]=ii2[minp]-1;
				minp=i;
			}
			else if(ii[i]>=ii[0]){
				for(int j=i-1;j>=0;j--){
					if(ii[i]<ii[j]){
						ii2[j]++;
					}
					else if(ii2[i]<=ii2[j]){
						ii2[i]=ii2[j]+1;
					}
				}
			}
			else{
				for(int j=i-1;j>=0;j--){
					if(ii[i]>ii[j]){
						ii2[j]--;
					}
					else if(ii2[i]>=ii2[j]){
						ii2[i]=ii2[j]-1;
					}
				}
			}
		}

		for(int i=0;i<ii.length;i++){
			ii3[ii2[i]-ii2[minp]]=ii[i];
		}
		
		return ii3;
	}			
	
	
	int[] SimpleSortSpeedy(int[] ii){           
		for(int i=0,j=ii.length-1;i<=j;i++,j--){
			int imin=ii[i],imax=ii[i],k1=i,k2=j;
			for(int i2=i+1;i2<=j;i2++){
				
				if(ii[i2]<imin){
					imin=ii[i2];
					k1=i2;
				}
				if(ii[i2]>imax){
					imax=ii[i2];
					k2=i2;
				}

			}
			ii[k1]=ii[i];
			ii[i]=imin;
			ii[k2]=ii[j];
			ii[j]=imax;
		}
		return ii;
	}
}

ナイス博士「どうだ！私のソートは早いだろう？」

BB君「うーーーん、さすがですね。どうやったんですか？」

ナイス博士「インデックスソートは、最初の数字のインデックスを０として、次の数字がそれ より大きければ１を足し、少なければ１を引いて比較対象とし、、次がさらにそれより大きければ１を足し、 少なければ１を引いて比較対象とし、次がさらにそれより大きければ１を足し、少なければ１を引いて 比較対象とし、次がさらに..........」

BB君「いいです、もういいです。でも、それだけでは説明がつきませんね。値が中間の時はどう するんですか」

ナイス博士「うーん、よく分からん！適当にやっていたら出来たんだ！いいじゃないか！」

BB君「ええっ、まあいいです。でも、シンプルソートスピーディーは分かりやすいし、 for文の使い方がユニークですね。」

ナイス博士「うん、あれも適当にやっていたら出来たんだ。」

BB君「いい加減だなあ。所長なのに。」

そよ風さん「ふたりで何やってるんですか？」

ナイス博士「やあ、BB君とソートをやっていたんだ。」

...続く

研究課題に戻る。