package sorting;

public class QuickSortUoPeople {
    private static boolean isDebugMode = false;
    private static int exchangeCount = 0;
    private static int compareCount = 0;

    public static void main(String[] args)
    {
        int ary[] = {12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77}; // course requirement
//        int ary[] = {1,2,3,4,5,6,7,8,9,75,1,2,3,4,5,6,7,7,7,7}; // when pivot is the max one
//        int ary[] = {100,102,103,104,105,106,75,102,103,102,101,100,104}; // when pivot is the min one

        System.out.println("size: " + ary.length);
        System.out.println("Original: ");
        printAry(ary, 0, ary.length-1);

        myQuickSort(ary, 0, ary.length-1);

        System.out.println("Sorted:");
        printAry(ary, 0, ary.length-1);
        System.out.println("compareCount: " + compareCount);
        System.out.println("exchangeCount: " + exchangeCount);
    }

    static void myQuickSort(int[] ary, final int startIndex, final int endIndex){
        if (isDebugMode) System.out.println("STEP01 - check the current sub-array: ");
        printAry(ary, startIndex, endIndex);

        // 1. find the pivot for the current sub-array
        int pivotIndex = findPivotIndex(ary, startIndex, endIndex);
        if (isDebugMode) System.out.printf("STEP02 - findPivotIndex ary[%d]:%d %n", pivotIndex, ary[pivotIndex]);

        // 2. move the pivot to the end of the current sub-array
        if (isDebugMode) System.out.println("STEP03 - Move pivot to the last index:  - pivot: " + ary[pivotIndex]);
        swapValInAray(ary, pivotIndex, endIndex);
        pivotIndex = endIndex;
        printAry(ary, startIndex, endIndex);

        // 3. puts things into left and right chunks
        if (isDebugMode) System.out.println("STEP04 - Arrange into two sub-arrays: ");
        int pivotFinalIndex = quickSortHelper(ary, startIndex, endIndex - 1, pivotIndex); // endIndex - 1 in order to remove pivot in the process

        // 4. in the end, return the final index which will be the index for the current pivot
        if (isDebugMode) System.out.println("STEP05 - Swap the current pivot with the returned index - pivot: " + ary[pivotIndex]);
        swapValInAray(ary, pivotIndex, pivotFinalIndex);
        printAry(ary, startIndex, endIndex);
        if (isDebugMode) System.out.println("END    =========================================================");

        if (pivotFinalIndex - 1 > startIndex) myQuickSort(ary, startIndex, pivotFinalIndex - 1);
        if (pivotFinalIndex + 1 < endIndex) myQuickSort(ary, pivotFinalIndex + 1, endIndex);


    }

    private static int quickSortHelper(int[] ary, int startIndex, int endIndex, int pivotIndex) {
        int debugStartIndex = startIndex;
        int debugEndIndex = endIndex;

        while(startIndex != endIndex){
            // find one number from the left part which is > pivot
            while(startIndex < endIndex && !(ary[startIndex] > ary[pivotIndex])) {
                startIndex++;
                compareCount++;
            }
            // find one number from the right part which is <= pivot
            while(endIndex > startIndex && !(ary[endIndex] <= ary[pivotIndex])) {
                endIndex--;
                compareCount++;
            }

            if (isDebugMode) System.out.printf("       ary[%d]=%d <-> ary[%d]=%d %n" , startIndex, ary[startIndex], endIndex, ary[endIndex]);

            swapValInAray(ary, startIndex, endIndex);
            printAry(ary, debugStartIndex, debugEndIndex);

        } // end while


        if (ary[startIndex] >= ary[pivotIndex]) return startIndex;
        else {return startIndex + 1;}
//
//        return startIndex + 1;
    }

    static int findPivotIndex(int[] ary, int startIndex, int endIndex) {
        return (startIndex + endIndex)/2;
    }

    private static void swapValInAray(int[] ary, int i, int j){
        int tmp = ary[i];
        ary[i] = ary[j];
        ary[j] = tmp;

        exchangeCount++;

//        printAry(ary);
    }

    private static void printAry(int[] ary, int start, int end){
        System.out.print("       ");
//        for (int i = start; i <= end; i++){
//            System.out.print(ary[i] + " ");
//        }
        for (int i = 0; i < ary.length; i++){
            if (start <= i && i <= end)
                System.out.printf("%3d " , ary[i]);
            else
                System.out.printf("%3s " , " ");
        }
        System.out.println();
    }

    private static void printAry(int[] ary){
        for (int i = 0; i < ary.length; i++){
            System.out.print(ary[i] + " ");
        }
        System.out.println();
    }

}