第４話 最大値排除繰り返し法時間計測版
解答コード例
class nr{
public static void main(String args[])throws IOException{
BufferedReader a=new BufferedReader(new InputStreamReader(System.in));
System.out.println("データ数をキーボードから入力してください。");
System.out.print ("データ数＝");
int n;
n=Integer.parseInt(a.readLine());
int[] x=new int[100000];
f(x,n); //ランダムデータ発生
System.out.println("ランダムデータ");
h(x,n); //データ表示
System.out.println();
double hj = System.currentTimeMillis();
g(x,n); //並び替え
double ow = System.currentTimeMillis();
System.out.println();
System.out.println("データの並び替え");
h(x,n); //データ表示
System.out.println();
System.out.println("並び替えにかかった時間は"+(ow-hj)/1000+"秒です。");
}
ではコードの核となる部分を説明します。
public static void g(int x[],int n){
int i,j,mx,w,jk=0;
for(i=0;i<n;i++){
mx=0;
for(j=i;j<n;j++){
if(mx<x[j]){
mx=x[j];
jk=j;
}
}
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
}
}
２次元ループ頭が混乱しますよね。
このプログラムの最大のミソは、for(j=i;j<n;j++)にあります。
最大値を除いてデータ対象群を小さくしていくには、j=i;とすればよいのです。
そして、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
は、見つかった最大値を排除しています。
