直線的な時間比較のベースで並べ替え

Question

私は、最初にソートされ、次に次のアルゴリズムでシャッフルされた配列をアンシャッフルする比較ベースのアルゴリズムの擬似コードを書くタスクを与えられました。アルゴリズム実行時間は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からの最悪の線形時間での選択についても知っていますが、これを組み合わせて正しいアルゴリズムを得るにはどうすればよいですか？

Answer 1

シャッフルされた配列は、RまたはL配列の要素の順序を乱すことはありません。どちらもシャッフルされた配列に含まれていますが、その要素はインターリーブされています。

中央値を計算して（線形時間で行うことができます）、それを使ってRとLを再度作成し直してシャッフルを元に戻すことができます。