如何计算快速排序算法中元素比较的次数？

Question

当给定一个元素数组时，我应该如何计算算法执行的元素比较次数？

这并不像只需将计数器添加到分区方法一样简单。

private void partition(int low, int high) {
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    int pivot = numbers[low + (high-low)/2];

    // Divide into two lists
    while (i <= j) {

        if (array[i] < pivot) {
            i++;
            compareCount++; //it's not as easy as just adding this here
        }
        else if (numbers[j] > pivot) {
            j--;
            compareCount++;
        }

        else (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

您不能这样做，因为它仅计算刚刚进行的比较，而不考虑在其评估为false时进行的任何比较。

我尝试将if（array [i]＜pivot）更改为while（array [i]＜pivot）（对于j也是如此），但如果以这种方式进行，我感觉还是错过了某些东西。

- David

---

不要返回翻译后的文本，只需翻译内容即可：您需要计算交换次数而非返回。我认为我无法理解您实际想要的是什么，请再明确一下。此外，在else if部分，为什么您要执行++ comparecounter？ - Algorithmist

我最初把它留在那里是因为当对一个由所有相等元素组成的数组进行排序时，这是我能够判断元素何时被排序的唯一方法。 - David

当你执行while(array[i]<pivot)时，你走在正确的道路上。在分区中进行一些修改就可以解决你的问题。 - Algorithmist

Answer 1

理想情况下，您应该能够通过分析逻辑来完成它。但是，如果您想在运行时让程序为您完成，则最简单的方法是编写一个用于执行比较操作的函数。让该函数每次被调用时都增加一个全局/静态变量，然后进行比较。在所有逻辑结束时，只需打印此全局/静态变量即可。

    public class Myclass{

    public static int compareCount = 0;

    }

    /*
    * PASS parameter comparisonMethod as following
    * 0 for ==, 1 for >, 2 for >=, 3 for < and 4 for <==
    *  Method returns true or false by doing appropriate comparison based on comparisonMethod 
    */

    public bool compare(int i, int j, int comparisonMethod)
    {
      Myclass.compareCount++;
      if(comparisionMethod ==0) return i==j?true:false;
      if(comparisionMethod ==1) return i>j?true:false;
      if(comparisionMethod ==2) return i>=j?true:false;
      if(comparisionMethod ==3) return i<j?true:false;
      if(comparisionMethod ==4) return i<=j?true:false;   
    }


    private void partition(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = numbers[low + (high-low)/2];

        // Divide into two lists
        while (compare(i, j, 4)) {

            if (compare(array[i], pivot, 3)) {
                i++;
            }
            else if (compare(numbers[j], pivot, 2)) {
                j--;
            }

            else (compare(i, j, 4)) {
                exchange(i, j);
                i++;
                j--;
            }
        }
// At the end of the logic, Myclass.compareCount wil give number of comparisons made.

- PraveenGorthy

---

我认为您不需要第一个或最后一个比较，因为它们只是元素“位置”变量，而不是它们正在比较的实际元素。在这种情况下，如果您删除这两个，它是否仍然捕获每个单独的元素比较？ - David

你不觉得你把事情复杂化了吗？我认为在Partition程序中进行简单修改就可以解决问题。请检查我的算法。 - Algorithmist

@David 由于每次比较都会调用compare函数，因此它应该能够捕获所有内容。 @Algorithmist 我实际上想通过将计算比较逻辑与分区方法分开来简化问题。我觉得这样做比把所有东西都绑在一起更容易处理。话虽如此，这只是一种方法。还有其他的方法，比如你提出的那种方法。 - PraveenGorthy

Answer 2

快速排序的分区方法将被调用，直到数组大小不为1为止，此时我们的数组将被排序。在您的代码中，当您找到要交换枢轴的位置（在else if部分）时，不应增加comparecounter。

您可以使用这个修改过的分区方法

partition(A,p,r)
{

    pivot=A[r]; // Taking last element as pivot
    i=p;
    j=r;

    while (true)
    {

        while(A[i] < pivot && i <= r )
        {

            ++comparecounter;
            ++i;

        }

        while(A[j] >= pivot && j >= 0)
        {

            --j;
            ++comparecount;

        }

        if(i < j)
        {

            Exchange A[i] and A[j]

        }
        else
        {
            return j;
        }

在上面的算法中，您可以将countcompare作为全局变量，并在每次调用分区时增加它。这将计算所做的比较次数。

- Algorithmist

Answer 3

你可以将比较计数的增量嵌入到每个if语句中...

    if ((compareCount++ != -1) && (array[i] < pivot))
    ...
    else if ((compareCount++ != -1) && (numbers[j] > pivot))
    ...
    else if ((compareCount++ != -1) &&  (i <= j))

它将始终评估 if 的第一个从句，始终返回 true，然后始终执行第二个从句。

- Chris Nash