/*
Randomised quick sort implementation in C language.
In normal quick sort, pivot chosen to partition is either the first or the last element of the array.
This can take time O(n*n) to sort in the worst case.
Now in randomised quick sort, pivot is randomly chosen and then recursively sort the left and right sub-arrays.
The expected running time of the algorithm is O(nlog(n)).
*/
#include
#include
#include

int getBig(int a[], int i, int right, int pivot)
{
    for(int k = i; k  pivot)
            return k;
    }
    return right+1;
}

int getSmall(int a[], int j, int left, int pivot)
{
    for(int k = j; k >= left; k--)
    {
        if (a[k] < pivot)
            return k;
    }
    return -1;
}

void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

void random_quick(int a[], int left, int right)
{
    if (left>=right)
        return;
    int index = left + (rand()%(right-left)), i = left, j = right;
    int pivot_index = index;
    int pivot = a[index];
    // storing index of element greater than pivot
    i = getBig(a, i, right, pivot);
    // storing index of element smaller than pivot
    j = getSmall(a, j, left, pivot);
    while(i j && pivot_index>i)
    {
        // case 1. When the pivot element index is greater than both i and j
        swap(&a[i], &a[pivot_index]);
        random_quick(a, left, i-1);
        random_quick(a, i+1, right);
    }
    else if (pivot_index