0

OrderElements次の関数を実装するにはどうすればよいですか？

char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length);

// chars now contains: c, e, d, a, b

線形の余分なスペースを使用できる場合は簡単ですが、一定の余分なスペースのみで実行できますか？つまり、chars要素をインプレースで直接並べ替えることができますか？

PS：これは試験問題ではありませんでした。私は実際にこの関数が必要です。

明確化：要素の望ましい最終的な順序について誤解があるようです。chars例の結果の配列には、元の配列を参照して、次の要素が含まれている必要があります。

{chars[2], chars[4], chars[3], chars[0], chars[1]}

これは

{'c', 'e', 'd', 'a', 'b'}.
4

6 に答える 6

6

ただし、厳密に言えば、O(lg length)リストのインデックスを表すにはメモリが必要です。iただし、64 ビットを使用することは、実際に並べ替えることができるすべてのものに対しておそらく十分に大きいため、この議論ではこれを無視します。

for (int i = 0; i < length; i++) {
  int t = want_order[i];
  while (t < i) {
    // t has been moved already; we need to find out where the value that started there
    // went. Since we must've put it at want_order[t] before, resume looking there
    t = want_order[t];
    // once t >= i, we know we've not touched that slot more than once, and so our
    // value is there
  }
  swap(chars[i], chars[t]);
}

直感的な説明: 配列内の各項目に対して、目標値を入れ、目標値を含むスロットに古い値を格納します。目標値が置き換えられた場合に対処するように注意する必要があります。これは、特定のスロットが 2 回までしかスワップされないことに注意することで処理されます。そこの値が別の値によって盗まれたとき (この反復がそれを行うため、発生することはありませんでした)、または最終値を挿入するために値が置き換えられたとき (これはインデックスが低い場合にのみ発生します)。

これがサンプル データでどのように見えるかを示す図:

 i | want_order | chars     | t
 0 |  2 4 3 0 1 | a b c d e | 2 (swap)
 1 |  2 4 3 0 1 | c b a d e | 4 (swap)
 2 |  2 4 3 0 1 | c e d a b | 3 (swap)
 3 |  2 4 3 0 1 | c e d a b | 0 (follow)
 3 |  2 4 3 0 1 | c e d a b | 3 (swap - no-op)
 4 |  2 4 3 0 1 | c e d a b | 1 (follow)
 4 |  2 4 3 0 1 | c e d a b | 4 (swap - no-op)

このアルゴリズムはO(lg n)メモリ (インデックス用) のみを使用しますが、実行時間を完全に分析することは試みていません。最悪であることは明らかですがO(n^2)、実際にはそれよりもうまくいくと思います。ただし、従わなければならない可能性のあるチェーンの長さに実際の制限はないため、原則として、実際にO(n^2)は最悪の場合の入力で時間を使用することになります。

于 2009-09-27T21:47:23.657 に答える
1

不可能。

ソートされた要素のインデックスを知るには、少なくとも O(log (list size)) が必要です。

于 2009-09-27T21:49:24.750 に答える
0

これで の仕事ができO(n²)ます。外側のループの各反復では、現在必要な要素が正しい位置にスワップされ (最初の内側のループ)、残りの要素の必要な順序が新しい状況を反映するように調整されます (2 番目の内側のループ)。

for (int i = 0; i < length; i++)
{
    for (int j = wantedOrder[i]; j > i; j--)
    {
        Swap(chars, j, j - 1);
    }

    for (int j = i + 1; j < length; j++)
    {
        if (wantedOrder[j] < wantedOrder[i])
        {
            wantedOrder[j]++;
        }
    }
}

もちろん、これには必要な順序配列を破棄する必要があります。これが許可されていない場合、問題を解決する方法がわかりません (少なくとも現時点では)。

于 2009-09-28T03:08:55.173 に答える
0

want_order 配列の変更が許可されている場合は実行できます。順列はサイクルに分解できるため、アルゴリズムはかなり単純です。1 つのサイクルを反復するときは、アクセスした各サイクルをマークするだけです。時間計算量は O(N) です。擬似コード:

char chars[]      = {'a', 'b', 'c', 'd', 'e'};
int  want_order[] = {2, 4, 3, 0, 1};
int  length       = 5;

OrderElements(chars, want_order, length) {
  int i, j, k;

  for(i = 0; i < length; ++i) {
    if (want_order[i] == -1) continue;

    j = startPos = want_order[i];
    c = chars[i];
    do {
      swap(c, chars[j]);
      k = want_order[j];
      want_order[j] = -1;
      j = k
    } while(j != startPos);
  }
}
于 2009-09-28T08:07:12.647 に答える
0

上記の投稿にはエラーがあります (誤ってインデックスを上書きします)。修正版は次のとおりです。

char chars[]      = {'a', 'b', 'c', 'd', 'e'};
int  want_order[] = {2, 4, 3, 0, 1};
int  length       = 5;

OrderElements(chars, want_order, length) {
  int i, j, k;

  for(i = 0; i < length; ++i) {
    if (want_order[i] == -1) continue;

    j = startPos = want_order[i];
    c = chars[i];
    do {
      swap(c, chars[j]);
      k = want_order[j];
      want_order[j] = -1;
      j = k
    } while(j != startPos);
  }
}
于 2011-10-29T16:30:42.597 に答える
-1

メモリ O(1) でのソート操作はバブルソートですが、パフォーマンスは O(n²) です

http://en.wikipedia.org/wiki/Bubble_sort

于 2009-09-27T21:53:36.957 に答える