1

配列 A = <0, 15, 5, 1, 0, 20, 25, 30, 35, 40> があるとします。比較をカウントするコードを書くとき、カウンターをどこに追加するか混乱します。カウントが繰り返されるのではないかと心配しているからです。

それにもかかわらず、それは15の比較があると言います。これが正しいかどうかはわかりません。実際に比較対象はいくつあるでしょうか。

int InsertionSort(int A[], int n)
{
   int i, j, index, counter = 0;

   for (i=1; i < n; i++)
   {
      index = A[i];
      for (j=i-1;j >= 0 && A[j] > index;j--)
      {
         A[j + 1] = A[j];
         counter++;
      }
      A[j+1] = index;
      counter++;
   }
   return counter;
}

int main()
{
    int A[]= {5,4,3,2,1};
    int counter = 0;
    int n =5;
    counter = InsertionSort(A, n);
    printf("%d",counter);

    return 0;
}
4

2 に答える 2

4

15 の比較 (および 6 つのスワップ) があります。

compare: 0 <= 15, 5, 1, 0, 20, 25, 30, 35, 40
compare: 0, 15 > 5, 1, 0, 20, 25, 30, 35, 40
swap:    0, 5 - 15, 1, 0, 20, 25, 30, 35, 40
compare: 0 <= 5, 15, 1, 0, 20, 25, 30, 35, 40
compare: 0, 5, 15 > 1, 0, 20, 25, 30, 35, 40
swap:    0, 5, 1 - 15, 0, 20, 25, 30, 35, 40
compare: 0, 5 > 1, 15, 0, 20, 25, 30, 35, 40
swap:    0, 1 - 5, 15, 0, 20, 25, 30, 35, 40
compare: 0 <= 1, 5, 15, 0, 20, 25, 30, 35, 40
compare: 0, 1, 5, 15 > 0, 20, 25, 30, 35, 40
swap:    0, 1, 5, 0 - 15, 20, 25, 30, 35, 40
compare: 0, 1, 5 > 0, 15, 20, 25, 30, 35, 40
swap:    0, 1, 0 - 5, 15, 20, 25, 30, 35, 40
compare: 0, 1 > 0, 5, 15, 20, 25, 30, 35, 40
swap:    0, 0 - 1, 5, 15, 20, 25, 30, 35, 40
compare: 0 <= 0, 1, 5, 15, 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15 <= 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20 <= 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25 <= 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30 <= 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30, 35 <= 40
于 2012-10-14T23:34:18.043 に答える
1

私には、あなたのカウンターは間違った場所にあるように見えます。A = <3、2>とすると、アルゴリズムは1つの比較を使用しますが、counter=2を報告します。15が正解の場合、このエラーは発生しなかったか、何らかの理由でキャンセルされました。

15が本当に正しい答えであるかどうかを確認するには、これがカウンターを改善する方法です。まず、アルゴリズムは、条件の左から右への評価順序（ほとんどのプログラミング言語が準拠している）に依存しています。これが意味するのは、P = falseの場合、Qは（P && Q）で評価されないということです。左から右への評価順序が保証されていない場合、アルゴリズムはA [-1]>インデックス（プログラムをクラッシュさせるもの）を評価する可能性があります。正しくカウントする最も簡単な方法は、次のようにforループの接続詞を2つの別々の行に分割することです。

for (i=1; i < n; i++)
{
   index = A[i];
   for (j=i-1; j >= 0; j--)
   {
      // Every time this line is reached, a comparison will be performed
      counter++;
      if (A[j] > index)
      {
         A[j + 1] = A[j];
      }
   }
   A[j+1] = index;
}

これで問題が解決した場合は、結果をお知らせください。この回答に賛成票を投じてください。

于 2012-10-18T12:07:13.587 に答える