package algorithm.sort;

import java.util.Random;

/**
 *
 * Created by yixin on 2017-07-27.
 */
public class QuickSort {


    public static void main(String[] args) {

        int problemSize = 30;
        final Random random = new Random();

//        int[] data = new int[]{29,62,28,78,83,91,96,64,27,64};

        int[] data = new int[problemSize];
        for(int i = 0; i < problemSize; i ++) {
            data[i] = random.nextInt(100);
            System.out.println(data[i]);
        }


        quickSort(data, 0, data.length - 1);


        System.out.println(" -- Sorted --");
        for(int i = 0; i < problemSize; i ++) {
            System.out.println(data[i]);
        }

    }


    static void quickSort(int[] array, int left, int right) {
        // 判断条件很重要，否则会陷入递归爆炸
        if(left < right) {
            int p = partitionHoare(array, left, right);
            quickSort(array, left, p - 1);
            quickSort(array, p + 1, right);
        }
    }


    /**
     * Lomuto Partition Scheme
     *
     * <p>
     * Conquer Step : Choose an item p as the pivot
     * Then partition the items of a[i..j] into three parts: a[i..m-1], a[m], a[m+1..j]
     *
     * a[i..m-1] (possibly empty) contains items that are smaller than p.
     * a[m] is the pivot p.
     * a[m+1..j] (possibly empty) contains items that are greater than or equal to p.
     *
     * Then, recursively sort the two parts.
     * </p>
     *
     * <p>
     * Conquer step: Don't be surprised... We do nothing :O!
     * </p>
     *
     * Note:
     * This scheme degrades to O(n2) when the array is already sorted as well as when the array has all equal elements
     *
     *
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    static int partitionLomuto(int a[], int lo, int hi) {
        int p = a[lo]; // p is the pivot
        int m = lo; // S1 and S2 are initially empty
        for (int k = lo+1; k <= hi; k++) { // explore the unknown region
            if (a[k] < p) { // case 2
                m++;
                swap(a, m, k);
            }
        }
        swap(a, lo, m); // final step, swap pivot with a[m]
        return m; // return the index of pivot, to be used by Quick Sort
    }


    /**
     * Original Partition Schema By C.A.R. Hoare:
     *
     * <p>
     * Uses two indices that start at the ends of the array being partitioned,
     * then move toward each other, until they detect an inversion. Then swap these two elements.
     * </p>
     *
     * But also can not avoid O(n2) when the input array is already sorted.
     *
     *
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    static int partitionHoare(int a[], int lo, int hi) {
        int p = a[hi]; // select the first element as the pivot
        int i = lo;
        int j = hi-1;

        while(i < j) {

            while(a[i] <= p && i<j) {
                i++;
            }

            while(a[j] >= p && i<j) {
                j--;
            }

            swap(a, i, j);
        }

        if(a[i] >= p) {
            swap(a, hi, i);
        } else {
            j++;
            swap(a, hi, j);
        }

        return j;
    }




    // Simple Swap Function using a temp value
    static void swap(int[] array, int from, int to) {
        int temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }
}