安定したアルゴリズムであるブラックボックス配列ソートアルゴリズムを変更する

Question

Sort1を与えられたアルゴリズムとし、与えられた配列にします。 Sort1はf（n）の時刻に実行されます。 f（n）+ O（n）の時間に実行されるSort1を使用して、新しい安定したアルゴリズムSort2を作成する必要があります。

私は私の友人が提案された解決策があります。数が数（要素であるカップル（数、インデックス）にB内のすべての番号を変更するA.

のクローン配列Bを作成

• を）、indexはインデックス（Aの位置）です。それに
• Bポイント内のすべての要素がソートされたAの同じ番号のすべてのシーケンスのためにA.
• にA.
• 実行SORT1に対応する要素だ、のインデックスでフラッシュをソートしますフラッシュでSORT1を実行しますすべての要素。

は彼の解決策ですか？何か提案はありますか？感謝！ ありがとう！

Answer 1

元のデータをプライマリキーとして使用する新しい比較関数を作成します（比較のために元の比較関数を使用している可能性もあります）。それが等しい場合は、配列内の元の位置に配置します。