//cd c:\HPTak\Program\JavaBasic3\Package
//set CLASSPATH=.	
//javac QsortFile\QsortFile.java
//java QsortFile.QsortFile 300000

//クィックソート(乱数発生、数値比較)
package QsortFile;

import java.util.*;
import java.io.*;
import List.*;

public class QsortFile{
  static int n;
  public static void main(String[] args) throws IOException {
      ArrayList al = new ArrayList(10);
      n=Integer.valueOf(args[0]).intValue(); //乱数発生回数
      Random generator = new Random();
      for (int i=0; i < n; i++) {
            int rand = generator.nextInt();
            Integer rn = new Integer(rand);
            al.add(i,rn);
      }
      System.out.println("クィックソート " + n + " 件");
      FileWriter fw = new FileWriter("QsortFile/output300000.txt"); 
                             // FileWriterオブジェクト
      BufferedWriter out = new BufferedWriter(fw);  
                            // BufferedWriterオブジェクト   
      out.write("クィックソート " + n + " 件" + "\n");
      Date t1= new Date();
      long starttime=t1.getTime();      
      out.write("ソート結果 " + qsort2(al) + "\n");
      Date t2= new Date();
      long finishtime=t2.getTime();
      long processtime=finishtime-starttime;
      System.out.println("starttime = " + starttime + " finishtime = " + finishtime + " processtime = " + processtime);
      out.close();      // BufferedWriterオブジェクトのクローズ
  }


  static ArrayList qsort2(ArrayList al){
	if (al.isEmpty() || al.size() ==1) 
             return al;
        String firsts=al.get(0).toString();
        Integer first=Integer.decode(firsts); 
	ArrayList left=new ArrayList(10);
        ArrayList right=new ArrayList(10);
        al.remove(0);
        return partition2(left,first,right,al);  
  }

  static ArrayList partition2(ArrayList left,Integer first,ArrayList right,ArrayList bf) {
       for (int i=0; i < n; i++) {
         if (bf.isEmpty()) {
   	   ArrayList alt = qsort2(left);
    	   ArrayList alt2 = qsort2(right);
           Sentence st3 = new Sentence();
           return st3.sn3(alt,first,alt2);
         }
         String first2s=bf.get(0).toString();
         Integer first2=Integer.decode(first2s); 
        if (first.compareTo(first2)<0) {
              Fput fr = new Fput();
              right=fr.fput(first2,right);
        }  else {
              Fput fl = new Fput();
              left=fl.fput(first2,left);
        }
        Bf b = new Bf();
        bf=b.bf(bf);
      }
      System.out.println("partition2  error");
     return null;
  }
}

/*
C:\HPTak\Program\JavaBasic3\Package>set CLASSPATH=.
C:\HPTak\Program\JavaBasic3\Package>javac QsortFile\QsortFile.java
C:\HPTak\Program\JavaBasic3\Package>java QsortFile.QsortFile 200000

クィックソート 10000 件
starttime = 1095084599078 finishtime = 1095084600031 processtime = 953

クィックソート 10000 件
starttime = 1095084046609 finishtime = 1095084047640 processtime = 1031

クィックソート 100000 件
starttime = 1095084289937 finishtime = 1095084352000 processtime = 62063

クィックソート 200000 件
starttime = 1095084799093 finishtime = 1095085176765 processtime = 377672

クィックソート 200000 件
starttime = 1095117709703 finishtime = 1095118069140 processtime = 359437

クィックソート 300000 件
starttime = 1095119610093 finishtime = 1095120987656 processtime = 1377563
*/