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

package Qsort4;
import java.util.*;
import List.*;

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

public class Qsort4 {
  static int n=200000; 
   
  public static void main(String[] args) {
	ArrayList al = new ArrayList(10);
        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 + " 件");
  //      System.out.println("Qsort Start" + al);
        System.out.println("Qsort 結果" + qsort2(al));
  }

  static ArrayList qsort2(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 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);
//	      System.out.println("partition return:qsort(left)= " + alt);
    	   ArrayList alt2 = qsort2(right);
//	      System.out.println("partition return:qsort(right)= " + alt2);
           Sentence st3 = new Sentence();
//           Sentence st3 = new Sentence(alt,first,alt2);
//           return left;
           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();
//              Fput fr = new Fput(first2,right);
              right=fr.fput(first2,right);
        }  else {
              Fput fl = new Fput();
//              Fput fl = new Fput(first2,left);
              left=fl.fput(first2,left);
        }
        Bf b = new Bf();
//        Bf b = new Bf(bf);
        bf=b.bf(bf);
      }
      System.out.println("partition2  error");
     return null;
  }
}

/*
TO QSORT2 :L
  IF :L = [ ] [OP [ ]]
  IF ( BF :L ) = [ ] [OP :L]
  OP PARTITION2 [ ] FIRST :L [ ] BF :L
END

TO PARTITION2 :LEFT :X :RIGHT :L
  REPEAT 9999
    [IF :L = [ ]
        [OP SE QSORT :LEFT  FPUT :X QSORT :RIGHT]
     IFELSE :X < ( FIRST :L )
        [MAKE "RIGHT FPUT FIRST :L :RIGHT]
        [MAKE "LEFT FPUT FIRST :L :LEFT]
     MAKE "L BF :L]
END
*/