/** autor: Edimar Chaves Jr.
 * 02/10/2019 13:40:33
 *
 * @param <T> T is a generic comparable type (Integer for exemple)
 *
 * The Three way quicksort it is an optimized version of traditional quicksort
 * this one deals better with several occurrences of elements equal to the pivot.
 **/

public class ThreeWayQuickSort<T extends Comparable<T>> {

    /** The main method.
     *
     * @param array a generic collection to be sorted.
     * @param left  the begin of the order.
     * @param right the end of the order.
     **/

    public void sort(T[] array, int left, int right) {

        if (left < right) this.partition(array, left, right);

    }

    /** The partition of array method.
     *
     * @param array a generic collection to partition.
     * @param left the begin of partition.
     * @param right the end of partition.
     */

    private void partition(T[] array, int left, int right) {

        if (left < right) {

            int start = left;
            int end = right;
            int i = left;
            T pivot = array[left];

            while (i <= end) {

                if (array[i].compareTo(pivot) < 0) {

                    this.swap(array, start, i);
                    start++;
                    i++;

                } else if (array[i].compareTo(pivot) > 0) {

                    this.swap(array, i, end);
                    end--;

                } else i++;

            }

            sort(array, left, start - 1);
            sort(array, end + 1, right);

        }
    }

    /**
     * The swap method.
     *
     * @param array a generic collection.
     * @param i the index of the element that will be swapped with the j-element.
     * @param j the index of the element that will be swapped with de i-element.
     */

    private void swap(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}