package sorting;

public class QuickSort_V3 {
    public static void main(String[] args)
    {
//        int[] ary = new int[]{40,3,59, -1, -999,4,6,99,888,7};
        int ary[] = {12,30,4,99,98,1,3,10,23,45,75,69,31,88,97,14,29,91,2,0,77};

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

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

    static void myQuickSort(int[] ary, int startIndex, int endIndex){
        // if the range of the sub-ary is empty or only has one element, there is no need to sort at all
        if (startIndex >= endIndex) {
            return;
        }

        // do the sorting
        Integer pivotIndex = myQuickSortHelper(ary, startIndex, endIndex);

        // divide the arrays into two sub-arrays and use the same sorting algorithm again
        myQuickSort(ary, pivotIndex+1, endIndex); // right side
        myQuickSort(ary, startIndex, pivotIndex-1); // left side
    }

    static Integer myQuickSortHelper(int[] ary, int startIndex, int endIndex){

        // the initial last smaller value index for this round
        int lastSmallerValueIndex = startIndex - 1;

        // execute the logic of quick sort
        int pivotVal = ary[endIndex]; // we pick the last element of the current range of sub-array as our pivot value
        System.out.printf("========= pivot - index: %d val: %d %n", endIndex, pivotVal);
//        System.out.printf("leftIndex: %d rightIndex: %d %n", startIndex, endIndex);
        for (int i = startIndex; i < endIndex; i++){
            int nowVal = ary[i];
//            System.out.printf("nowVal: %d - pivotVal: %d --- nowVal <= pivotVal: %b %n", nowVal, pivotVal, nowVal <= pivotVal);
            if (nowVal <= pivotVal) { // we found there is one number that is lower than the pivotValue, so we simply put it the the left side of the array
                lastSmallerValueIndex++;
                swapValInAray(ary, lastSmallerValueIndex, i);
                printAry(ary, startIndex, endIndex);
                System.out.println();
            }
        }

        // put pivotValue to the pivotIndex
        int pivotIndex = lastSmallerValueIndex + 1;
        swapValInAray(ary, pivotIndex, endIndex);
        printAry(ary, startIndex, endIndex);
        System.out.println(" - put pivotValue to the pivotIndex ");
        return pivotIndex; // this is the index that is set to have the current pivotVal forever
    }

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

//        printAry(ary);
    }

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

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