package Core;

public class PP4Partition
{
    public static void main (String args[])
    {
        Integer[] data1 = {5,4,7,8,3};
        Integer[] data2 = {7,4,1,1,5,6};

        quickSort(data1);
        quickSort(data2);
        for(int i = 0; i < data1.length; i++)
        {
            System.out.print(data1[i]);
        }
        System.out.println("");
        for(int i = 0; i < data2.length; i++)
        {
            System.out.print(data2[i]);
        }
    }

    public static <T extends Comparable<T>> void quickSort(T[] data)
    {
        quickSort(data, 0, data.length - 1);
    }

    private static <T extends Comparable<T>> void quickSort (T[] data, int min, int max)
    {
        if(min < max)
        {
            int indexofpartition = partition(data, min, max);
            quickSort(data, min, indexofpartition - 1);
            quickSort(data, indexofpartition + 1, max);
        }
    }

    private static <T extends Comparable<T>> int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int partitionindex;
        int left, right;
        int middle = (min + max)/2;
        left = min;
        right = max;

        if(left >= right && left <= middle || left <= right && left >= middle)
        {
            partitionindex = left;
        }
        else if (right >= left && right <= middle || right <= left && right >= middle)
        {
            partitionindex = right;
        }
        else //if (middle >= left && middle <= right || middle <= left && middle >= right)
        {
            partitionindex = middle;
        }

        partitionelement = data[partitionindex];
        swap(data, partitionindex, min);

        while(left < right)
        {
            while(left < right && data[left].compareTo(partitionelement) <= 0)
            {
                left++;
            }

            while(data[right].compareTo(partitionelement) > 0)
            {
                right--;
            }

            if(left < right)
            {
                swap(data, left, right);
            }
        }

        swap(data, min, right);
        return right;
    }

    /**
     * Swaps to elements in an array. Used by various sorting algorithms.
     *
     * @param data   the array in which the elements are swapped
     * @param index1 the index of the first element to be swapped
     * @param index2 the index of the second element to be swapped
     */
    private static <T extends Comparable<T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
}