package test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class QSort {

    public static void main(String args[]){
        System.out.println(qsort(Arrays.asList(1,5,6,2,11,9,4)));
    }

    public static List<Integer> qsort(List<Integer>list){
        if(list.size()==1){
            //配列の含まれる要素が一つならば、再帰処理を抜ける
            return new ArrayList<Integer>(list) ;
        }else{
            //リスト内の要素を分割する処理を呼び出す
            Divive div = splitList(list);
            //分割後の配列を格納するリストを生成する
            List<Integer>newList = new ArrayList<Integer>();
            //小さい数の集合を再度、切り分けるために再帰処理を行う
            newList.addAll(qsort(div.leftList));
            //大きい数の集合を再度、切り分けるために再帰処理を行う
            newList.addAll(qsort(div.rightList));
            return newList ;
        }
    }

    //リストを分割する関数
    public static Divive splitList(List<Integer>list){
        int size =list.size();
        Divive div = new Divive();
        //要素数が二つの場合は、要素間の大小を比較して要素分割を行う
        if(size==2){
            if(list.get(0)<=list.get(1)){
                div.leftList.add(list.get(0))  ;
                div.rightList.add(list.get(1))  ;
            }else{
                div.leftList.add(list.get(1))  ;
                div.rightList.add(list.get(0))  ;
            }
            return div;
        }

        int pivot = list.get(0);
        List<Integer>smallIntList =new ArrayList<Integer>();
        List<Integer>largeIntList =new ArrayList<Integer>();
        //引数で与えられたリストを所定の基準に従って、小さい集合と大きい集合に分ける
        for(int i=0;i<size;i++){
            //基準より小さい数の集合を生成する
            if(pivot>=list.get(i))smallIntList.add(list.get(i));
            //基準より大きい数の集合を生成する
            if(pivot<list.get(size - 1- i))largeIntList.add(list.get(size - 1- i));
        }

        //小さい集合と引数で与えられたリストの引数が一致しない場合、分割したリストの組み合わせを呼び出し元に戻す
        if(smallIntList.size()!=list.size()){
            div.leftList.addAll(smallIntList);
            div.rightList.addAll(largeIntList);
        }
        //小さい集合と引数で与えられたリストの引数が一致する場合は基準となる数字が一番小さいので、
        //リストの一番左とそれ以外でリストを分割する
        else{
            Deque<Integer> que  = new ArrayDeque<Integer>(smallIntList);
            div.leftList.add(que.pop()) ;
            div.rightList.addAll(new ArrayList<Integer>(que))  ;
        }
        return div;
    }

    //Javaは戻り値に2値を設定できないため、分割後の集合を表すデータ構造を定義しておく必要がある
    static public class Divive{
        List<Integer>leftList =new ArrayList<Integer>();
        List<Integer>rightList =new ArrayList<Integer>();
    }
}