c++ - 计算快速排序算法中组件明智比较的数量。

Question

我正在尝试计算我的快速排序算法对大小为 500 的数组进行的比较次数。我知道带分区的快速排序的最佳情况是 nlogn-n+1。因此，对于大小为 500 的数组，组件明智比较的最佳情况数约为 3983。但是，当我运行我的代码时，我得到 2400 次左右的比较，具体取决于随机函数生成的数组。我计算的组件明智比较的数量是错误的吗？请帮忙。

#include <iostream>
    #include <string>
    #include <stdlib.h>
    using namespace std;


    int count_500 = 0;

    int partition(int *S,int l, int u);
    void swap(int &val1, int &val2);
    void Quicksort(int S[],int low, int hi);
    void exchange(int list[], int p, int q);
    int median_of_3(int list[], int p, int r);
    void Quicksort_M3(int S[], int low, int hi);





    int main()
    {
            int S1_500[500];
            int S2_500[500];
            int S3_500[500];

            int S1_200[200];
            int S2_200[200];
            int S3_200[200];

            int S1_8[8];
            int S2_8[8];
            int S3_8[8];

            srand ( time(NULL) );



            for(int i=0; i<500; i++)
            {
                    S1_500[i] = rand()%1000;
                    S2_500[i] = rand()%1000;
                    S3_500[i] = rand()%1000;
            }

            for(int i=0; i<200; i++)
            {
                    S1_200[i] = rand()%500;
                    S2_200[i] = rand()%500;
                    S3_200[i] = rand()%500;
            }

            for(int i=0; i<8; i++)
            {
                    S1_8[i] = rand()%100;
                    S2_8[i] = rand()%100;
                    S3_8[i] = rand()%100;
            }

            Quicksort(S1_500,0,499);
            for(int i=0; i<500; i++)
            {
                    cout << S1_500[i] << endl;
            }

            cout << "Number of component wise comparisons is: " << count_500 << endl;





    }


    int partition(int *S,int l, int u)
    {
            int x = S[l];
            int j = l;
            for(int i=l+1; i<=u; i++)
            {
                    if(S[i] < x)
                    {       
                            count_500++; // Count the component wise comparison
                            j++;
                            swap(S[i],S[j]);
                    }
            }
            int p = j;
            swap(S[l],S[p]);
            return p;
    }

    void swap(int &val1, int &val2)
    {
            int temp = val1;
            val1 = val2;
            val2 = temp;
    }

    void Quicksort(int S[],int low, int hi)
    {
            if (low < hi)
            {
                    int p = partition(S,low,hi);
                    Quicksort(S,low,p-1);
                    Quicksort(S,p+1,hi);
            }
    }

Answer 1

您需要 if 语句之外的 count_500++;。您只对结果为 true 的比较进行计数。

改变

                if(S[i] < x) 
                {        
                        count_500++; // Count the component wise comparison 
                ...
                }

到

                count_500++; // Count the component wise comparison 
                if(S[i] < x) 
                {        
                ...
                }