Randomized Quick Sort algorithm - O(n log n) worst case complexity

The worst case time complexity of a typical implementation of Quick Sort is O(n²). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element, which happens when the input array is either sorted or reversely sorted and either first or last element is picked as pivot.

Randomized Quick Sort algorithm (with random pivot):

In the randomized version of Quick sort we impose a distribution on input by picking the pivot element randomly. Randomized Quick Sort works well even when the array is sorted/reversely sorted and the complexity is more towards O(n log n). (Yet, there is still a possibility that the randomly picked element is always an extreme.)

Here, we will pick a random pivot position with the help of rand() function (defined in stdlib.h header file). Then we can swap pivot element with the element at the Left position (or the Right position in some implementations) and Quick Sort the array.

void swap(int *A, int x, int y) {
    int temp;
    temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

int getPivot(int Left, int Right) {
    return ( rand() % (Right - Left + 1) ) + Left;
}

void quickSort(int *A, int Left, int Right) {
    if(Left > Right)
        return;
    
    int i, pos, pivot;

    // Choosing pivot element randomly:

    pivot = getPivot(Left, Right);  // Get a random pivot
    swap(A, Left, pivot);           // Take A[pivot] to Left index and then do Quick Sort

    // Quick Sort the array:

    pos = Left;
        
    for(i = Left+1; i <= Right; i++)
        if(A[i] < A[Left])
            swap(A, ++pos, i);

    swap(A, Left, pos);  // By now, pos must be at proper position for A[Left].
                         // So we swap A[Left] with A[pos]

    quickSort(A, Left, pos-1);     // Sort left sub-list
    quickSort(A, pos+1, Right);    // Sort right sub-list
}