algorithm - ベクトルの順列

Question

ベクトルがあるとします:

 0  1  2  3  4  5
[45,89,22,31,23,76]

そして、そのインデックスの順列:

[5,3,2,1,0,4]

このようにして得られる順列に従ってそれを再分類する効率的な方法はありますか:

[76,31,22,89,45,23]

最大で O(1) の追加スペースを使用しますか?

Answer 1

はい。左端の位置から始めて、その位置 i にある (他の) 誤って配置された要素と交換することにより、要素を正しい位置i に配置します。これは、O(1) の追加スペースが必要な場所です。この位置の要素が正しくなるまで、要素のペアを交換し続けます。そうして初めて、次の位置に進み、同じことを行います。

例：

[5 3 2 1 0 4] 初期状態

[4 3 2 1 0 5] スワップ (5,4)、5 は正しい位置になりましたが、4 はまだ間違っています

[0 3 2 1 4 5] スワップ (4,0)、4 と 0 の両方が正しい位置になり、次の位置に移動

[0 1 2 3 4 5] (3,1) を入れ替えて、1 と 3 がどちらも正しい位置にあるので、次の位置に移動します

[0 1 2 3 4 5] すべての要素が正しい位置にあります。終了。

注:

各スワップ操作は、(2 つのうちの) 少なくとも 1 つの要素を正しい位置に配置するため、そのようなスワップは全体で N 個を超える必要はありません。

Answer 2

ザックのソリューションは非常に優れています。

それでも、なぜソートする必要があるのか​​ 疑問に思っていました。インデックスの順列がある場合は、値を古い配列へのポインターとして使用します。

これにより、そもそも配列をソートする必要がなくなる場合があります。これは、すべての場合に使用できるソリューションではありませんが、ほとんどの場合は問題なく機能します。

例えば：

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

aの値を調べたい場合は、次のようなことができます (疑似コード):

for i=0 to 4
{
    process(a[i]);
}

新しい順序で値をループしたい場合は、次のようにします。

for i=0 to 4
{
    process(a[b[i]]);
}

前述のように、多くの場合、このソリューションで十分ですが、そうでない場合もあります。それ以外の場合は、Zach によるソリューションを使用できます。ただし、このソリューションを使用できる場合は、並べ替えがまったく必要ないため、より優れています。