计算快速排序比较 [英] counting quicksort comparisons

问题描述

我实现了一个简单的快速排序(下面的代码)，以计算快速排序进行的平均和最差比较.我声明了一个全局变量来保存计数器以进行比较.我将3个计数器放置在我认为可以对比较进行计数的不同位置上，问题是计数器总和与通过快速排序进行的比较总数的理论值不匹配.我试图解决这个问题几个小时，但很快就解决了.如果您能指出我应该在哪里放置柜台以及为什么要将它们放在那里，我将不胜感激.我假设计数器应该放在进行比较的地方.显然我错了.

I implemented a simple quick sort (code below) to count the average and worst comparison made by quicksort. I declared a global variable to hold the counter for comparisons. I placed 3 counters in different positions that I thought would count the comparisons, the problem is the counter sum does not match the theoretical value of the total number of comparisons made by quick sort. I tried to solve this problem for hours but came up short. I really appreciate if you can point me where I should put the counters and why I should place them there. I assumed a counter should go where ever a comparison is made. apparently I'm wrong.

public int[] quickSort(int[] array, int start, int end){


    if (start < end){
        counter++;//1st comparison here
        int pivot;  

        pivot = Partition(array, start, end);
        quickSort(array, start, pivot - 1);
        quickSort(array, pivot + 1, end );
    }
return  array;
}

private int Partition(int[] array, int start, int end) {
    int pivot = array[end];
    int i = start - 1;

    for(int j = start; j <= end - 1; j++){

        counter++;//2nd comparison here


        if (array[j] <= pivot){
            counter++;//3rd comparison here
            i = i + 1;

            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

    }

    int temp = array[i+1];
    array[i+1] = array[end];
    array[end] = temp;

    return i + 1;
}

推荐答案

从理论上讲，只计算数组元素的比较，不计算索引与边界的比较，因此，您只应保留第二个counter++;(您需要独立于比较结果而增加计数器.)

For the theory, only the comparisons of array elements are counted, not the comparisons of indices to the bounds, so you should only leave the second counter++; (you need to increment the counter independently of the result of the comparison).

然后是一个问题，您要与哪些理论值进行比较.快速排序有不同的实现方式，它们使用的比较次数略有不同.特别是，您对枢轴的选择不会尝试避免出现极端值，因此此实现将很容易退化为O(n ^ 2)行为.

Then there is the question against which theoretical values you compare. There are different implementations of quicksort which use slightly different numbers of comparisons. In particular, your choice of the pivot makes no attempt to avoid extreme values, so this implementation will easily degrade to O(n^2) behaviour.

这篇关于计算快速排序比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！