随机数据快速排序导致 N^2 复杂度图

Question

我正在尝试用快速排序的测量值绘制理论时间复杂度。当我输入递增、递减或恒定的数据系列时，快速排序的图看起来不错（它们很好地遵循 N^2）。当我输入随机输入流时出现问题。

对于给定随机数据的快速排序，时间复杂度为 n log n，但我的数据点表明它是 N^2。我尝试过应用不同的分区实现，并且确保元素得到排序。

这是我对快速排序和分区步骤的实现：

template<typename BidirectionalIterator, typename Compare>
BidirectionalIterator partition_impl(BidirectionalIterator first,
BidirectionalIterator last, Compare cmp) {
    auto pivot = std::prev(last, 1);
    if (first == pivot) return first;
    while (first != last) {
        while (cmp(*first, *pivot)) { ++first; } // search greater > pivot
        do { --last; } while (!cmp(*last, *pivot) && last >= first); // search < pivot
        if (first > last) {     // if left iterator has surpassed right iterator
            std::iter_swap(first, pivot);
            return first;
        }
        if (*first > *last) {
            std::iter_swap(first, last);
            ++first;
        }
    }
    std::iter_swap(first, pivot);
    return first;
}

template <typename FwdIt, typename Comp = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Comp cmp = Comp{}) {
    if (std::distance(first, last) <= 1) return;

    FwdIt split = partition_impl(first, last, cmp);

    quick_sort(first, split, cmp);  // sorts the left partition
    quick_sort(split + 1, last, cmp);   // sorts the right partition
}

所以我的问题是：在我的实现中有什么可以表明问题所在吗？

这是我的图表的样子：

编辑： 一些额外的代码：

void measure(std::vector<int>& ds) {
    Timer::start();
    algo_ptr(ds.begin(), ds.end(), std::less<>());
    Timer::stop();
}
void collectSamples(data_series_t& data_series) {
    for (int k = 0; k < NUM_OF_SAMPLES; ++k) {
        auto ds = std::get<1>(data_series)(x_measurement_point);
        measure(ds);
        measurements.push_back(Timer::elapsedTime());
    }
}

algo_ptr 直接进入我上面的实现。对于每个数据系列，我收集 10 个样本，在每次迭代中我确保生成一个新的随机数据系列，这样我就不会对已经排序的元素进行排序。

Answer 1

感谢大家的帮助。对此，我真的非常感激。我想我已经找到了解决方案。

问题是我只允许出现 50 个不同的随机值。这对于随机值的样本量来说太小了，因为我测量的元素比这多得多。

这本质上导致枢轴不是随机选择的，这使我的快速排序算法退化为 N^2。

事后看来，这似乎是我应该意识到的显而易见的事情，但我仍然是 DSA 的初学者。

在解决这个问题并确保我有几百万个不同的可能随机值之后，图表看起来像这样：

Answer 2

首先，

partition_impl

有一个bug会导致故障：

do { --last; } while (!cmp(*last, *pivot) && last >= first);

last >= first

比较需要在

cmp

调用之前完成，以防止使用超出范围的迭代器调用它。有趣的是，这在

arm64

上运行时导致了故障，但在

x86

上却没有。

其次，这里是

std::sort

和

quick_sort

之间的性能比较。第一张图显示了从 1M 到 20M 行排序时经过的时间，第二张图显示了每种算法所需的比较次数。

我怀疑您的算法具有 O(n log n) 行为，但库版本在选择枢轴方面做得更好（我认为它使用三种方法的中值），这导致速度提高可能只是一个常数因子。