Quicksort无法一致地对10万个整数的数据集进行排序

Question

我已经在C ++中实现了Quicksort算法的几种变体，但它们都有一个很大的缺陷。他们无法在合理的时间内对10万个整数的数据集进行排序。有时，10 000个整数的数据集也会失败，但频率会降低很多。最初，我怀疑我选择的枢轴导致了问题，但即使随机选择了一个数据透视表，算法也无法在合理的时间内执行。有人可以帮我确定我的Quicksort实现性能不佳的原因吗？

下面是我使用固定数据透视表实现的Quicksort。

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]);
    }
}

要测试我的Quicksort算法的矢量100 000无序整数，我使用以下代码：

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);
}

可以针对各种矢量大小here测试代码

Answer 1

代码中的两个问题：首先，oldPivot是索引而不是数据透视值。代码将其用作值。将其更改为索引以消除混淆。

其次，对quicksort的呼吁在oldPivot的任何一方都在推进，而不是只推进一种方式。

此外，在分配随机向量时使用reserve以在内部仅引起一次内存分配。

#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);

}