QuickSort and Randomized Quicksort

Question

I want to know the usage of QuickSort and randomized QuickSort.
Please help me when to use what?

Answer 1

Quicksort worst case performance is o(n^2) when list is already sorted which is same as bubble sort. To avoid worst case performance we use randomized quick sort which uses random partition. See the following code -

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

int randomPartition(int* arr, int start, int end)
{
    int pivotIdx, pivot, i, j;

    srand(time(NULL));
    pivotIdx = start + rand() % (end-start+1);
    pivot = arr[pivotIdx];
    swap(&arr[pivotIdx], &arr[end]); // move pivot element to the end
    pivotIdx = end;
    i = start -1;

    for(j=start; j<=end-1; j++)
    {
        if(arr[j] <= pivot)
        {
            i = i+1;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i+1], &arr[pivotIdx]);
    return i+1;
}

void randomQuickSort(int* arr, int start, int end)
{
    int mid;
    if(start < end) {
        mid = randomPartition(arr, start, end);
        randomQuickSort(arr, start, mid-1);
        randomQuickSort(arr, mid+1, end);
    }
}

void main()
{
    int A[] = {20,50,70,10,100,80,90};
    int i = 0;

    randomQuickSort(A, 0,6);
    for (i=0;i<7;i++)
        printf("%d \n", A[i]);
}