0

このコードでは、これはどのように機能しますか (Java):

/** Move A[A.length-1] to the first position, k, in A such that there
* are no smaller elements after it, moving all elements
* A[k .. A.length-2] over to A[k+1 .. A.length-1]. */

static void moveOver (int A[]) {
   moveOver (A, A.length-1);
}

/** Move A[U] to the first position, k<=U, in A such that there
* are no smaller elements after it, moving all elements
* A[k .. U-1] over to A[k+1 .. U]. */

static void moveOver (int A[], int U) {
  if (U > 0) {
    if (A[U-1] > A[U]) {
      /* Swap A[U], A[U-1] */
     moveOver (A, U-1);
    }
  }
}

これは、オンラインで受講しているバークレーCSクラスから取得し、独学しています。それは宿題ではありません（私はそれが幸運ではありませんでした）。私が理解していないのは次のとおりです。

A[] の数値が 8、2、10、5、4、12 であるとします。上記でそれらを使用すると、反復でこれを取得し、トレースします。

  1. 最上部の添字は U、またはこの場合は 12、U-1 は 4、スワップは行われません
  2. U は 4 (再帰 U-1) になり、その上の数字は 5 (もう 1 つの U-1) になります。彼らは交換されます。
  3. 4 が上に移動したため、U は 4 になり、10 は U-1 で交換されます。

私のシーケンスは現在 8,2,4,10,5,12 です。

私の質問は、すでに通過した番号を取得するにはどうすればよいですか? たとえば、テストのためにその添え字に戻らない場合、どうすれば 5 つ上に移動できますか。

プログラムを正しくトレースしているとは思えず、再帰と混同されています。このため、スワップが正しく行われたと仮定してください。

ありがとうございました。

せ

4

2 に答える 2

1

問題に対するあなたの誤解の鍵は、実際にはあなたの質問のタイトルに隠されていると思います

挿入ソートを理解するのに助けが必要

アルゴリズムは実際には現在の要素のみを並べ替えますが、要素が配列に追加されるたびに実行されるという考え方です。そうすれば、呼び出されるたびに、配列の残りの部分がすでに順番になっています。言い換えれば、あなたはその最後の要素の位置にソートしようとしているだけです。

したがって、例の番号（8、2、10、5、4、12）を使用し、それらを一度に1つずつ配列に追加/並べ替えると、順序は次のようになります（各ステップでの並べ替えは、すでに行っている方法とまったく同じです）。説明）：

To be added         | old array      | after push     | Result (after moveOver())
(8, 2, 10, 5, 4, 12)| []             | [8]            | [8]
(2, 10, 5, 4, 12)   | [8]            | [8,2]          | [2,8]
(10, 5, 4, 12)      | [2,8]          | [2,8,10]       | [2,8,10]
(5, 4, 12)          | [2,8,10]       | [2,8,10,5]     | [2,5,8,10]
(4, 12)             | [2,5,8,10]     | [2,5,8,10,4]   | [2,4,5,8,10]
(12)                | [2,4,5,8,10]   | [2,4,5,8,10,12]| [2,4,5,8,10,12]
于 2010-01-28T21:51:15.553 に答える
0

トレースに関しては、条件が満たされないため、ポイント2で間違っているifため、再帰呼び出しは行われません。

再帰が混乱する場合は、反復形式に書き直すと役立つ場合があります。

static void moveOver (int A[], int U) {
  while (U > 0 && A[U-1] > A[U]) {
    /* Swap A[U], A[U-1] */
    --U;
  }
}

これで、小さな要素に遭遇するとすぐにループが停止することが簡単にわかります。これを完全なソート アルゴリズムにするには、さらに作業が必要です。いずれにせよ、これは挿入ソートではありません。私には部分的なバブルソートのように見えます。

このコードはどこから入手したと言いましたか?

于 2010-01-28T21:45:16.030 に答える