第７話 最大値排除繰り返し法２重自己再帰版
解答コード例
import java.io.*;
class nk{
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(0,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 f(int x[],int n){
int i;
for(i=0;i<n;i++)x[i]=(int)(Math.random()*100);
}
public static void h(int x[],int n){
int i;
for(i=0;i<n;i++){
if(i>0 && i%20==0)System.out.println();
if(x[i]<10)System.out.print(" "+x[i]+" ");
if(x[i]>=10)System.out.print(x[i]+" ");
}
}
public static void g(int s,int x[],int n){
int ik,w;
ik=p(s,0,s,x,n);
if(ik>s){
w=x[s];
x[s]=x[ik];
x[ik]=w;
}
if(s+1<n-1)g(s+1,x,n);
}
public static int p(int ik,int mx,int s,int x[],int n){
if(mx<x[s]){
mx=x[s];
ik=s;
}
if(s+1<n){
ik=p(ik,mx,s+1,x,n);
}
else{
return(ik);
}
return(ik);
}
}
実行例
さて、隣項交換繰り返し法と最大値排除繰り返し法のどちらが速いかの実験結果をお見せしましょう。
データ数は１００００です。
隣項交換繰り返し法(for文２次元版)
最大値排除繰り返し法(for文２次元版）
軍配は、最大値排除繰り返し法に上がりました。
約９倍の速さでした。
さて、これで第１７講は終了です。第１８講では素数探索・完全数探索・フィボナッチ数列探索に挑みます。
第６話へ 第18講第１話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第２部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
