5

私はバブルソートのバージョンを持っています:

int i, j;  

for i from n downto 1 
{
    for j from 1 to i-1 
    { 
        if (A[j] > A[j+1])
            swap(A[j], A[j+1]) 
    } 
}

上記のバージョンのバブル ソートを使用して、期待されるスワップ数を計算したいと考えています。私が使用した方法を以下に示します。

// 0 based index

float ans = 0.0;

for ( int i = 0; i < n-1; i++ )
{
    for ( int j = i+1; j < n; j++ ) {

        ans += getprob( a[i], a[j]); // computes probability that a[i]>a[j].
    }
}

私は正しい道を進んでいますか、それとも何かが欠けていますか?

4

3 に答える 3

5

答えを得る最善の方法は、バブル ソート アルゴリズム自体を実行し、swap() 呼び出しの後にカウンターを含めることです。あなたの計算関数は、（a）ソート自体（swap（）とgetprob（）のランタイムに応じて）とほぼ同じ時間が必要であり、（b）ソート中に要素の順序が変わるという点を見逃します。

ところで、swap() 呼び出しの正確な数は、並べ替える必要があるデータによって異なります。n*(n-1)/2 の比較があり、それらのいずれかがスワップになる可能性があります (平均して、必要な時間の半分)比較された要素を交換します)。

于 2012-07-04T15:04:07.240 に答える
2

たぶんこれが役立ちます。基本的に、これは一連のシミュレーション データセットに対してバブル ソートを実行し、スワップ確率を計算するためのフレームワークを提供します。

この確率を p とすると、予想されるスワップ操作の数を見つけるには、これを実際のデータセットに適用する必要があります。このデータセットのサイズを n とします。次に、期待される数 = swapProbability * n * n

n*n は、バブル ソートの予想操作数が n * n であるためです。

float computeSwapProbability()
{
    int aNumSwaps = 0
    int aTotalNumberOfOperations = 0

    For all simulation datasets
    {


        int i, j;  

        for i from n downto 1 

        { 

            for j from 1 to i-1 

            { 
                aTotalNumberOfOperations++

                if (A[j] > A[j+1]) 
                {
                    swap(A[j], A[j+1]) 
                    aNumSwaps++
                }

            } 

        }
    }

    return (float)aNumSwaps/aTotalNumberOfOperations;
}
于 2012-07-04T15:10:31.193 に答える