0

私はc ++を使用しており、挿入ソートを使用しています

挿入ソートアルゴリズムのどこにカウンターを配置して、アイテムの移動数とアイテムの比較数を監視する必要がありますか。以下にセットアップを含めました

void InsertionSort::insertion_sort()
{
    int key,i,count = 0;
for(int j=1;j<10;j++)
 {
    key=Arr1[j];
    i=j-1;
    while(Arr1[i]>key && i>=0)
    {
     Arr1[i+1]=Arr1[i];
     i--;
     numberOfItemMovements++;
    }
    Arr1[i+1]=key;
}
}
}

ご覧のとおり、アイテム移動カウンターは良好で期待どおりに機能しますが、比較カウンターをどこに置くべきかわかりません。ありがとう

4

2 に答える 2

1

これを機能させる方法は、ループで numberOfComparisons を使用することです。

while(++numberOfComparisons && Arr1[i]>key && i>=0)
{
    Arr1[i+1]=Arr1[i];
    numberOfItemMovements++;
    i--;
}

++numberOfComparisons1) while ループで使用できるのにnumberOfComparisons++失敗する理由を理解していますか?

2) Arr1[-1] が評価される問題があります。これがどこで起こっているのか、コードを変更して修正する方法を理解できますか?

于 2012-06-13T14:32:07.547 に答える
0

移動カウンターは確かに正しいです。

比較カウンターを実装するには、コードを少し再構築する必要があります。Arr1[i]>key特に、とを区別できる必要がありますi>=0。一方は比較を必要とし、もう一方は比較を必要としないためです。

これは宿題のように見えるので、残りはあなたに任せます。

于 2012-06-13T14:27:34.693 に答える