Static notes

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

The Quicksort algorithm consists of three steps:

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

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

 1#include <iostream>
 2#include <cstdlib>
 3#include <algorithm>
 4
 5template <typename T>
 6void printArray(T *array, size_t size)
 7{
 8    for (size_t i = 0; i < size; ++i) {
 9        std::cout << array[i] << " ";
10    }
11    std::cout << std::endl;
12}
13
14template <typename T>
15void quickSort(T *array, size_t left, size_t right)
16{
17    size_t l = left;
18    size_t r = right - 1;
19    size_t size = right - left;
20
21    if (size > 1) {
22        T pivot = array[rand() % size + l];
23
24        while (l < r) {
25            while (array[r] > pivot && r > l) {
26                r--;
27            }
28
29            while (array[l] < pivot && l <= r) {
30                l++;
31            }
32
33            if (l < r) {
34                std::swap(array[l], array[r]);
35                l++;
36            }
37        }
38
39        quickSort(array, left, l);
40        quickSort(array, r, right);
41    }
42}
43
44int main(void)
45{
46    size_t size = 21;
47    int *array = new int[size];
48
49    for (int i = 0; i < size; ++i) {
50        array[i] = (100.0 * rand()) / RAND_MAX;
51    }
52
53    printArray(array, size);
54    quickSort(array, 0, size);
55    printArray(array, size);
56
57    delete [] array;
58
59    return 0;
60}

Randomized quicksort implementation in C++