//cd c:\HPTak\Program\JavaBasic3\Qsort
//set CLASSPATH=.	
//javac Qsort2.java
//java Qsort2

//クィックソート(乱数発生、数値比較)
import java.util.*;

public class Qsort2 {
   
  public static void main(String[] args) {
	ArrayList al = new ArrayList(10);
        int n=1000;  //乱数の発生回数 1200 ではStackOverflowError
        Random generator = new Random();
        for (int i=0; i < n; i++) {
        	int rand = generator.nextInt()/1000000;
                Integer rn = new Integer(rand);
                al.add(i,rn);
        }
        System.out.println("クィックソート" );
        System.out.println("Qsort Start" + al);
        System.out.println("Qsort 結果" + qsort(al));
	}

  static ArrayList qsort(ArrayList al){
	if (al.isEmpty() || al.size() ==1) 
             return al;
        //Integer first=(Integer)al.get(0); ClassCastException
        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 partition(left,first,right,al);  
 }

  static ArrayList partition(ArrayList left,Integer first,ArrayList right,ArrayList bf) {
       if (bf.isEmpty()) {
   	   ArrayList alt = qsort(left);
    	   ArrayList alt2 = qsort(right);
           Sentence2 st3 = new Sentence2(alt,first,alt2);
           return st3.sn3(alt,first,alt2);
         }
        String first2s=bf.get(0).toString();
        Integer first2=Integer.decode(first2s); 
        bf.remove(0);
        if (first.compareTo(first2)<0) {
              right.add(0,first2);
              return partition(left,first,right,bf);
        }  else {
              left.add(0,first2);
              return partition(left,first,right,bf);
        }
    }
}