Quicksort fails to consistently sort data sets of 100 000 integers

Question

I have implemented several variations of the Quicksort algorithm in C++, but they all share a big flaw. They fail to sort data sets of 100 000 integers in a reasonable amount of time. Sometimes, data sets of 10 000 integers also fail, but a lot less frequently. Initially, I suspected that my choice of pivot was causing the issue, but even when a pivot was chosen randomly the algorithm failed to execute in a reasonable amount of time. Can someone help me identify the cause of the poor performance of my Quicksort implementation?

Below is my implementation of Quicksort with a fixed pivot.

void quicksort(std::vector<int> &list, int left, int right)
{
    if (left >= right)
       return;
    int pivot = list[left + (right - left) / 2];
    int oldPivot = partition(list, pivot, left, right);
    quicksort(list, left, oldPivot - 1);
    quicksort(list, oldPivot + 1, right);
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (true)
    {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        // Stop when the pivot is reached.
        if (left >= right)
            return left;
        std::swap(list[left], list[right]);
    }
}

To test my Quicksort algorithm for a vector 100 000 unordered integers I use the following code:

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());
    assert(vector == expectedVector);
}

The code can be tested for various vector sizes here

Answer 1

Two problems in the code: First, oldPivot is an index and not a pivot value. The code uses it as a value. Changed this to index to remove the confusion.

Second, the calls to quicksort were advancing on either side of oldPivot, rather than advancing only one way.

Also, use reserve when allocating the random vector to cause only one allocation of memory internally.

#include <vector>
#include <list>
#include <random>
#include <algorithm>
#include <iostream>


void quicksort(std::vector<int> &list, int left, int right);
int partition(std::vector<int> &list, int pivot, int left, int right);
int randomize_pivot(int left, int right);
std::vector<int> randomizeIntVector(int size);

void print_vector(std::vector<int> v, int left, int right)
{
    for (int i = left; i <= right; i++) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

void quicksort(std::vector<int> &list, int left, int right)
{

    if (left >= right)
        return;
    int pivot = list[left + (right - left) / 2];
    int index = partition(list, pivot, left, right);
    quicksort(list, left, index - 1);
    quicksort(list, index, right);  // prior was 'index + 1', which skipped a cell
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (left <= right) {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        if (left <= right) {
            std::swap(list[left], list[right]);
            left++;
            right--;
        }
    }
    return left;
}

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    vector.reserve(size);
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

std::vector<int> smallVector(int size)
{
    std::vector<int> vector1{5, 4, 1, 2, 3};

    return vector1;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());

    assert(vector == expectedVector);

}