0

この選択ソートですべての比較を追跡する必要がありますが、1000 のリストから値に対して返される値は 1 つだけです。正しく実装したかどうかはわかりませんが、比較カウントを正しく配置したことは確かです/ . 通常、選択ソートには一定量のキー比較がありますが、インストラクターはそれらを追跡するための数式の使用を禁止しています。この出力が返される理由に興味があります。

comp = 1
swap = 1 

template <class elemType>
void selectionSort(elemType list[], int length)
{
    int loc, minIndex;
    int first; 
    int last, second;
    int swaps =0;
    int comp = 0;

    minIndex = first;
    for (loc = 0; loc < length; loc++)
    {
        comp+=1; 

        for(loc = first +1; loc<=last; loc++)
        {
            comp+=1;
            if(list[loc]<list[minIndex])
                minIndex=loc;
            comp+=1;
        }
        elemType temp;
        temp= list[first];
        list[first]= list[second];
        list[second] = temp;


        swaps+=1;
    }

    //  comp = (length *(length-1)/2);

    cout<<"swaps= "<<swaps<<endl;
    cout<<"comps= "<<comp<< endl;
}

どんな考えでも大歓迎です

4

1 に答える 1

1

並べ替え自体が機能していないと思います。lastfirstおよびsecond変数(特に)を適切に初期化してから、lastそれらを移動(インクリメント)する必要があります。

last変数はデフォルトで。0loc<=lastで設定されているため、2番目のforループの条件が原因で、必要に応じて反復が実行されません。私はあなたがそれを次のように初期化する必要があると思います:

 last = length-1;

もう1つの問題があります。両方のループで、同じインデックス変数を使用していますloc。2つの異なる変数を使用する必要があると思います。

for (loc = 0; loc < length; loc++)
{
  comp+=1; 
   for(loc = first +1; loc<=last; loc++)
   {

完全な並べ替えを実行するようにロジックを修正すると、正しいカウントが得られます。

于 2012-11-02T19:08:45.313 に答える