import java.util.Random;


public class QuickSort {
    public static int N = 20;
    public static int[] sequence = new int[N];

    public static void QuickSort(int left, int right){
        if( right - left <= 0){
            return;
        }
        else{
            Random rand = new Random();
            int pivotIndex = left + rand.nextInt(right - left + 1);
            swap(pivotIndex, right);

            int pivot = sequence[right];
            int partition = partitionInt(left,right,pivot);
            QuickSort(left, partition -1);
            QuickSort(partition+1, right);
        }
    }

    private static void swap(int d1, int d2) {
        int aux = sequence[d1];
            sequence[d1] = sequence[d2];
            sequence[d2] = aux;

    }

    private static int partitionInt(int left, int right, int pivot) {
        int leftPtr = left;
        int rightPtr = right;

        while(leftPtr <= rightPtr){
            while(right > 0 && sequence[right] > pivot){
                right--;
            }
            while(sequence[left] < pivot){
                left++;
            }
            if( leftPtr >= rightPtr ){
                swap(sequence[leftPtr], sequence[rightPtr]);
                left++;
                right--;
            }
        }
        swap(sequence[left],sequence[right]);
        return leftPtr;
    }
    static void printSequence(int[] sorted_sequence)
    {
        for (int i = 0; i < sorted_sequence.length; i++)
            System.out.print(sorted_sequence[i] + " ");
    }

    public static void main(String args[])
    {
        System.out
                .println("Sorting of randomly generated numbers using RANDOMIZED QUICK SORT");
        Random random = new Random();

        for (int i = 0; i < N; i++)
            sequence[i] = Math.abs(random.nextInt(100));

        System.out.println("\nOriginal Sequence: ");
        printSequence(sequence);
        System.out.println("\nSorted Sequence: ");
        QuickSort(0, N - 1);
        printSequence(sequence);
    }
}