//cd c:\HPTak\Program\JavaBasic3\Qsort
//set CLASSPATH=.	
//javac Qsort.java
//java Qsort 6
//java Qsort 6 2
//java Qsort 6 2 9
//java Qsort 6 2 5
//java Qsort 6 9 2 5
//java Qsort 3 9 4 7 5 1 8 6 2 
//java Qsort c d f e g a k b f

//クィックソート
import java.util.*;

public class Qsort {
   
 public static void main(String[] args) {
	//リストとその要素を作成する
	ArrayList al = new ArrayList(10);
        //コマンドライン引数をargsで受け取りリストに。
        for (int i=0; i<args.length; i++)
        	al.add(i,args[i]);
        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;
        String  first=al.get(0).toString();
        ArrayList left=new ArrayList(10);
        ArrayList right=new ArrayList(10);
        al.remove(0);
        return partition(left,first,right,al);  
 }

  static ArrayList partition(ArrayList left,String first,ArrayList right,ArrayList bf) {
       if (bf.isEmpty()) {
   	   ArrayList alt = qsort(left);
//	      System.out.println("partition return:qsort(left)= " + alt);
    	   ArrayList alt2 = qsort(right);
//	      System.out.println("partition return:qsort(right)= " + alt2);
   //        Sentence st3 = new SentenceOverride(alt,first,alt2);
           Sentence st3 = new Sentence(alt,first,alt2);
           return st3.ss3(alt,first,alt2);
         }
        String  first2=(bf.get(0)).toString();
        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);
        }
    }
}

/*
TO QSORT :L
  IF :L = [ ] [OP [ ]]
  IF ( BF :L ) = [ ] [OP :L]
  OP PARTITION [ ] FIRST :L [ ] BF :L
END

TO PARTITION :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

TO PARTITION2 :LEFT :X :RIGHT :L
  IF :L = [ ]
    [OP SE QSORT :LEFT FPUT :X QSORT :RIGHT]
  IF :X < ( FIRST :L )
    [OP PARTITION :LEFT :X FPUT FIRST :L :RIGHT BF :L]
  OP PARTITION FPUT FIRST :L :LEFT :X :RIGHT BF :L
END

C:\HPTak\Program\JavaBasic>java List/Qsort c d f e g a k b f
クィックソート
Qsort Start[c, d, f, e, g, a, k, b, f]
Qsort 結果[a, b, c, d, e, f, f, g, k]

Qsort Start[3, 9, 4, 7, 5, 1, 8, 6, 2]
Qsort 結果[1, 2, 3, 4, 5, 6, 7, 8, 9]

Qsort Start[6, 9, 2, 5, 7]
Qsort 結果[2, 5, [], 6, [7, [9]]]

C:\HPTak\Program\JavaBasic>java List/Qsort 6 2 9
Qsort 結果[2, 6, [9]]

C:\HPTak\Program\JavaBasic>java List/Qsort 6
Qsort 結果[6]

C:\HPTak\Program\JavaBasic\Quicksort2>java Qsort 6 2
Qsort 結果[2, 6, []]


C:\HPTak\Program\JavaBasic>java List/Qsort 6 9 7 5
クィックソート
Qsort Start[6, 9, 7, 5]
partition return:first= 6 right= [7, 9]
partition return:qsort2(left)= [5]
Exception in thread "main" java.lang.StackOverflowError

java List/Qsort 6 であって、java List\Qsort 6 不可
C:\HPTak\Program\JavaBasic>java List\Qsort 6
Exception in thread "main" java.lang.NoClassDefFoundError: List\Qsort (wrong nam
[9, 8, 2, 5, 7]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size:
0
Qsort.java:41: シンボルを解決できません。
シンボル: メソッド addall (java.lang.String)
場所    : java.util.ArrayList の クラス
            if (left.addall(first)){
                    ^

1 ArrayList bf2=(ArrayList)bf;
  return (qsort2(left).add(first).add(qsort2(right));
C:\HPTak\Program\JavaBasic\Quicksort>javac Qsort.java
Qsort.java:41: シンボルを解決できません。
シンボル: メソッド addall (java.lang.String)
場所    : java.util.ArrayList の クラス
            return qsort2(left).addall(first).addall(qsort2(right));
                         ^
エラー 1 個

2 ArrayList bf2=ArrayList(bf);
  return (qsort2(left).add(first).add(qsort2(right)));

Qsort.java:38: シンボルを解決できません。
シンボル: コンストラクタ ArrayList (java.lang.Object)
場所    : java.util.ArrayList の クラス
       ArrayList bf2=new ArrayList(bf);
                     ^
Qsort.java:41: boolean は間接参照できません。
            return (qsort2(left).add(first).add(qsort2(right)));
                          ^
エラー 2 個
*/

/*
別のプログラム
class Qsort {
   public static void main(String[] args) {
	//リストとその要素を作成する
	ArrayList al = new ArrayList(10);
        //コマンドライン引数をargsで受け取りリストに。
        for (int i=0; i<args.length; i++)
        	al.add(i,new Integer(args[i]));
        //リストの要素を表示する
        System.out.println(al);
        System.out.println("クィックソート" );
        qsort2(al,args.length);
        System.out.println(al);
	}

  static void qsort2(ArrayList al,int n){
	int i=0;
	int j=n-1;
	int pivot=Integer.parseInt(al.get((i+j)/2).toString());
	while (j>0) {
		int a =Integer.parseInt(al.get(i).toString());
		int b =Integer.parseInt(al.get(j).toString());
             System.out.println("i= " + i + " j= " + j +  " a = " + a +  " b = "                    + b +  " pivot = " + pivot);
		//Loop
                while (a< pivot) 
			i++;
		while (b > pivot)
			j--;
		if (i >= j) {
                        System.out.println("i= " + i + " j= " + j );
			return;
                }
		String hold=al.get(i).toString();
		String s=al.get(j).toString();
		al.set(i,s);
		al.set(j,hold);
              System.out.println("i= " + i + " j= " + j + " "+ al);
		i++;
		j--;
	}
	if (i-1>0)
		qsort2(al,i);
	if (j+2<n)
		qsort2(al,n-j-1);
//		qsort2(al+j+1,n-j-1);
  }
}

C:\HPTak\Program\JavaBasic\Quicksort>java Qsort 9 8 2 5 7
[9, 8, 2, 5, 7]
クィックソート
i= 0 j= 4 a = 9 b = 7 pivot = 2

Qsort.java:40: シンボルを解決できません。
シンボル: メソッド set (int)
場所    : java.util.ArrayList の クラス
                al.set(i)=al.get(j);
                  ^
Qsort.java:41: シンボルを解決できません。
シンボル: メソッド set (int)
場所    : java.util.ArrayList の クラス
                al.set(j)=hold;
                  ^
Qsort.java:48: 演算子 + は java.util.ArrayList,int に適用できません。
                qsort2(al+j+1,n-j-1);
                         ^
Qsort.java:48: Qsort の qsort2(java.util.ArrayList,int) は (java.lang.String,int
) に適用できません。
                qsort2(al+j+1,n-j-1);
                ^
エラー 4 個
*/