A={1,2,3,4}、p={36,3,97,19}、p をソート キーとして A をソートするとします。{2,4,1,3} を取得できます。
これは、アルゴリズム入門書の例です。nlognでできると書いてあります。
どうすればそれができるかについて、誰かが私にアイデアを教えてもらえますか？私の考えでは、p[1] が p[3] で終わり、A[1] が A[3] で終わるように、p の各要素を追跡して、それがどこで終わるかを見つける必要があります。誰でもこれを行うためにマージソートまたは他のnlognソートを使用できますか?
私はアルゴリズムが初めてで、少し威圧的だと思います:(助けてくれてありがとう。
インデックス配列を作成します。
i = { 0, 1, 2, 3 }
ここで、ソート中pに、インデックス配列に同じ変更を加えますi。
完了すると、次のようになります。
i = { 1, 3, 0, 2 }
2 つの配列を並べ替えると、1 つを並べ替える場合の最大 2 倍の時間がかかります (実際には、比較のみをカウントする場合は、追加の比較を行う必要はなく、1 つではなく 2 つの配列でデータを交換するだけです)。ソート全体の Big-O の複雑さを変更しますO( 2n log n ) = O(n log n)。
Aこれで、これらのインデックスを使用して、並べ替えられたインデックス配列を反復処理し、そのインデックスの要素を検索するだけで、並べ替えられた配列を線形時間で構築できますA。これにはO( n )時間がかかります。
アルゴリズム全体の実行時の複雑さは最悪です。O( n + 2n log n ) = O( n log n )
もちろん、インデックス配列を完全にスキップして、配列Aを同じように扱い、 side に沿って並べ替えることもできますp。
並べ替えアルゴリズムの複雑さは通常、必要な比較の数で測定されるAため、これは難しいとは思いませんB。B複雑さは同じであるため、並べ替えに既に必要なものに加えて、比較を行う必要はありません。
要素を移動するたびに、両方の配列で移動するだけで完了です。