Randomized quicksort implementation in C++

2013-11-07
#cpp #quicksort #howto #snippet

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:

  1. Choose reference element called pivot (in randomized version pivot choise is random)
  2. 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
  3. 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:

 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}