QuickSort 最好的情况比平均情况更糟

Question

我有一个关于快速排序的恼人问题。所以，我必须研究快速排序在最佳、平均和最坏情况下的性能（在操作中）。

操作包括：比较 + 归因。

目前我在这种情况下测试快速排序（100 到 10.000 个元素数组）。当我测试它时出现问题，我得到以下结果（例如 100 个元素数组）：

最佳情况： 大约。 4853 次操作

平均情况： 大约。 1468 次操作

最坏情况： 大约。 9024 次操作

理论上说，QuickSort 在 最佳和平均 两种情况下的效率都是 O(n*log n)。如您所见，我得到了一个完全不同的结果，这违反了理论。

（我使用 Profiler 作为自定义库来生成随机数组。FillRandomArray 方法的最后一个参数是顺序（0 - 无序，1 - 升序，2 - 降序））。

这是我使用的代码：

#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include "Profiler.h"

#define MIN_SIZE 100
#define MAX_SIZE 10000


struct sortingAlg{
        std::string type;
        int atributions;
        int comparisons;
};

int partition(int *givenArray, int p, int r, sortingAlg& sortingAlgoritm)
{
        int x = givenArray[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; ++j)
        {
                sortingAlgoritm.comparisons += 1;
                if (givenArray[j] <= x)
                {
                        sortingAlgoritm.atributions += 2;
                        i += 1;
                        int aux = givenArray[i];
                        givenArray[i] = givenArray[j];
                        givenArray[j] = aux;
                }
        }

        sortingAlgoritm.atributions += 2;
        givenArray[r] = givenArray[i + 1];
        givenArray[i + 1] = x;
        return i + 1;
}

void quicksort(int *givenArray, int beginning, int length, sortingAlg& sortingAlgoritm)
{
        if (beginning < length)
        {
                int q = partition(givenArray, beginning, length, sortingAlgoritm);
                quicksort(givenArray, beginning, q-1,  sortingAlgoritm);
                quicksort(givenArray, q + 1, length, sortingAlgoritm);
        }
}

int main()
{
        Profiler profiler("heapProfiler");

        sortingAlg sortingAlgs[2];
        sortingAlgs[0].type = "HS";
        sortingAlgs[0].atributions = 0;
        sortingAlgs[0].comparisons = 0;

        sortingAlgs[1].type = "QS";
        sortingAlgs[1].atributions = 0;
        sortingAlgs[1].comparisons = 0;


        for (int i = MIN_SIZE; i <= MAX_SIZE; i += 100)
        {
                std::cout << "Sorting array for " << i << " elements.." << std::endl;


                sortingAlgs[1].atributions = 0;
                sortingAlgs[1].comparisons = 0;

                int *avg =  new int[i];
                FillRandomArray(avg, i, 0, 1000, false, 0);
                quicksort(avg, 1, i, sortingAlgs[1]);

                profiler.countOperation("AVG_QuickSort_ALL", i, sortingAlgs[1].atributions + sortingAlgs[1].comparisons);
                profiler.createGroup("AVG_QuickSort", "AVG_QuickSort_ALL");

                sortingAlgs[1].atributions = 0;
                sortingAlgs[1].comparisons = 0;

                int *best =  new int[i];
                FillRandomArray(best, i, 0, 1000, false, 1);
                quicksort(best, 1, i, sortingAlgs[1]);

                profiler.countOperation("BEST_QuickSort_ALL", i, sortingAlgs[1].atributions + sortingAlgs[1].comparisons);
                profiler.createGroup("BEST_QuickSort", "BEST_QuickSort_ALL");

                sortingAlgs[1].atributions = 0;
                sortingAlgs[1].comparisons = 0;


                int *worst = new int[i];
                FillRandomArray(worst, i, 0, 1000, false, 2);
                quicksort(worst, 1, i, sortingAlgs[1]);

                profiler.countOperation("WORST_QuickSort_ALL", i, sortingAlgs[1].atributions + sortingAlgs[1].comparisons);
                profiler.createGroup("WORST_QuickSort", "WORST_QuickSort_ALL");
        }
        std::cout << "Building complete...! Creating profiler groups... Opnening reports!" << std::endl;
        profiler.showReport();


        return 0;
}

有什么想法吗？谢谢

Answer 1

我觉得你选择pivot的时候有问题

对于 "best case" 场景，您应该选择 "best pivot"，但您没有这样做。如果你总是选择 pivot 作为中间的数字，它会起作用。

Answer 2

简短的回答是，看起来您没有正确选择枢轴以便成为（甚至接近）最佳情况。事实上，考虑到您似乎是如何选择枢轴的，令我惊讶的是，按顺序对数据进行排序并不比您显示的更糟糕。

为了使有序数据成为最佳情况，您希望选择枢轴作为当前正在分区的部分中间的元素。在这种情况下，您不必移动任何元素来进行分区。

顺便说一句：IMO，您的代码不必要地难以阅读。例如，p 和 r 作为参数名称几乎没有意义。更好的名字将极大地帮助破译您的代码。同样，除非您有非常具体的理由不这样做，否则我也会考虑更换您的：

                    int aux = givenArray[i];
                    givenArray[i] = givenArray[j];
                    givenArray[j] = aux;

类似：

using std::swap;
// ...


                   swap(givenArray[i], givenArray[j]);

这不仅更具可读性，而且对于使用 int 以外的某种类型的元素的代码可能更有效，对于这些元素，最有效的交换可能不是复制整个元素。

就个人而言，如果我想像您一样分析比较和赋值的计数，我会采取完全不同的方式：我会定义一个类型来跟踪该类型的比较和赋值：

template <class T>
class counted {
    static size_t comparisons;
    static size_t assignments;
    T val;
public:
    counted(T val) : val(val) {}
    bool operator<(counted c) {
        ++comparisons;
        return val < c.val;
    }

    counted &operator=(counted &other) { 
        ++assignments;
        val = other.val;
        return *this;
    }
    static void reset() { 
        assignments = 0;
        comparisons = 0;
    }
    std::pair<size_t, size_t> counts() { 
        return std::make_pair(assignments, comparisons); 
    }
};

然后排序代码将只进行排序，要分析排序代码，您只需传递一个处理分析的这种类型的数组（或最好是向量）。排序完成后，您可以从该类型中检索计数、重置计数并进行下一个测试。这样，您几乎可以分析任何排序代码，而无需重写排序代码来进行分析（例如，如果您想将快速排序与 std::sort 的各种输入顺序进行比较，您可以很容易地这样做）。

QuickSort 最好的情况比平均情况更糟

QuickSort best case is worst than average case

c++

algorithm

quicksort