私は、最初にソートされ、次に次のアルゴリズムでシャッフルされた配列をアンシャッフルする比較ベースのアルゴリズムの擬似コードを書くタスクを与えられました。アルゴリズム実行時間はtheta(n)である必要があります。私は左Subarry Lからインデックスを持つすべての項目をshuffelingた後、A '[I ... + N2 i]をわたってるしきあること。見つけた直線的な時間比較のベースで並べ替え
Shuffle(int[] A)
n1 = A.length+1/2 // floordiv
n2=A.lenght-n1
L = L[n1]
R = R[n2]
L[1...n1] = A[1...n1]
R[1...n2] = A[n1+1...A.length]
i=j=1;
for k=1 to A.length do
b=Random(0,1) // returns 0 or 1 equally likely
if(b == 0 and i<= n1) or j>n2 then
A[k] = L[i]
i++;
else
A[k] = R[j]
j++;
右のサブアレイRからのインデックスiを持つすべてのアイテムは、A '[i-n2 ... i]の間にあります。 解決策には中央値を見つけることが含まれていますが、どのように役立つのか分かりません。
また、私はCormenのIntroduction to Algorithmsからの最悪の線形時間での選択についても知っていますが、これを組み合わせて正しいアルゴリズムを得るにはどうすればよいですか?
この質問は、SOよりもCSスタックエクスチェンジに適しています。 – jrook
*しかし、それがどう役立つか分かりません。シャッフルされた配列の値は、 'L'または' R'配列から値をランダムに選択することによって作成されます。これらの配列は元の配列の中央値に基づいて作成されます。この事実を利用して、シャッフルされた配列から 'R'と' L'を再作成してシャッフルを取り消すことができます。 – jrook
ありがとう、私はそれを投稿するつもりでしたが、私は40分待つ必要があります。 – moepmoep12