package alice.test.codesegment.local.bitonicsort;

public class Sort {

    // this method has "stack overflow" problem
    public static void quickSort(DataList data){
        int[] stack = new int[8192];
        int sp = 0;
        int begin = 0;
        int end = data.table.length-1; // index is up to length-1
        while(true){
            while(begin < end){
                if (end-begin< 40){
                    bubbleSort(data,begin,end);
                    break;
                } else {
                    int where = (begin+end)/2;
                    int pivot = data.table[where];
                    data.table[where] = data.table[begin];
                    int p = begin;
                    for (int i=begin+1;i<=end;i++){
                        if (data.table[i]<pivot){
                            p++;
                            if (i!=p)data.swap(p,i);
                        }
                    }
                    data.table[begin] = data.table[p];
                    data.table[p] = pivot;
                    stack[sp++] = p+1;
                    stack[sp++] = end;
                    end=p-1;
                }
            }
            if (sp==0) return;
            end = stack[--sp];
            begin = stack[--sp];

        }
    }

    public static void bubbleSort(DataList data ,int begin,int end){
        for (int i=begin;i<end;i++){
            for (int j=end;j>i;j--){
                if (data.table[i] > data.table[j]){
                    data.swap(i,j);
                }
            }
        }


    }

    public static void check(DataList data){
        System.out.println("checking ....");
        for (int i = 0; i< data.table.length-1; i++){
            if (data.table[i] > data.table[i+1]){
                System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i);
                return;
            }
        }
        System.out.println("sort is succeed");
    }
}