Bikulov's blog

Quicksort has $O(N\log(N))$ computational complexity in best and average cases, $O(N^{2})$ for bad case. Extremely bad cases may be avoided by using randomized Quicksort.

Qucksort algorithm consists of three steps:

Choose reference element called pivot (in randomized version pivot choise is random)
Rearrange array so that all elements smaller than pivot are placed before the pivot in array, all elements bigger than pivot are placed after the pivot
Call Quicksort for elements before the pivot and Quicksort for elements after the pivot recursively (stop if array size is one or less)

My implementation of Quicksort in C++ is provided below. quicksort.cpp:

#include <iostream>
#include <cstdlib>
#include <algorithm>

template <typename T>
void printArray(T *array, size_t size)
{
    for (size_t i = 0; i < size; ++i) {
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;
}

template <typename T>
void quickSort(T *array, size_t left, size_t right)
{
    size_t l = left;
    size_t r = right - 1;
    size_t size = right - left;

    if (size > 1) {
        T pivot = array[rand() % size + l];

        while (l < r) {
            while (array[r] > pivot && r > l) {
                r--;
            }

            while (array[l] < pivot && l <= r) {
                l++;
            }

            if (l < r) {
                std::swap(array[l], array[r]);
                l++;
            }
        }

        quickSort(array, left, l);
        quickSort(array, r, right);
    }
}

int main(void)
{
    size_t size = 21;
    int *array = new int[size];

    for (int i = 0; i < size; ++i) {
        array[i] = (100.0 * rand()) / RAND_MAX;
    }

    printArray(array, size);
    quickSort(array, 0, size);
    printArray(array, size);

    delete [] array;

    return 0;
}

Randomized quicksort implementation in C++