1

クイックソート アルゴリズムが 500 の配列サイズに対して行う比較の数を数えようとしています。パーティションを使用したクイックソートの最適なケースは nlogn-n+1 であることがわかっています。したがって、配列サイズが 500 の場合、コンポーネントごとの比較の最良のケース数は約 3983 になります。ただし、コードを実行すると、random 関数が生成する配列に応じて、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);
            }
    }
4

1 に答える 1

3

あなたはステートメントのcount_500++;外側が欲しいです。if結果がである比較のみをカウントしていますtrue。

変化する

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

に

                count_500++; // Count the component wise comparison 
                if(S[i] < x) 
                {        
                ...
                }
于 2012-10-17T06:43:07.690 に答える