16

次の質問に出くわしました。

n 個の要素の配列とk < nの整数kが与えられます。要素 { a 0 ... a k } および { a k +1 ... a n } は既にソートされています。O( n ) 時間と O(1) 空間でソートするアルゴリズムを与えてください。

O( n ) 時間と O(1) 空間で実行できるようには思えません。問題は、マージソートのマージステップをインプレースで行う方法を実際に尋ねているようです。可能であれば、マージソートはそのように実装されませんか? 私は自分自身を納得させることができず、意見が必要です。

4

3 に答える 3

9

これは、O(lg^2 n) 空間で実行できることを示しているようです。定数空間でのマージが不可能であることを証明する方法がわかりませんが、それを行う方法もわかりません。

編集: 参照の追跡、Knuth Vol 3 - 演習 5.5.3 には、「L のかなり複雑なアルゴリズムがあります。Trabb-Pardo は、この問題に対する最良の回答を提供します: O(n) 時間で安定したマージを行うことが可能であり、安定しています。 O(n lg n) 時間でソートし、固定数のインデックス変数に O(lg n) ビットの補助メモリのみを使用します。

私が読んでいないより多くの参考文献。興味深い問題をありがとう。

さらに編集: この記事では、Huang と Langston による記事には、サイズ m と n の 2 つのリストを時間 O(m + n) でマージするアルゴリズムがあると主張しているため、質問に対する答えは「はい」と思われます。残念ながら私は記事にアクセスできないので、中古の情報を信頼する必要があります。これを、Trabb-Pardo アルゴリズムが最適であるという Knuth の宣言とどのように調和させるべきかわかりません。私の人生がそれにかかっているなら、私はクヌースと一緒に行きます.

これは以前のスタック オーバーフローの質問として何度も尋ねられていたことがわかります。重複としてフラグを立てる心はありません。

黄 B.-C. および Langston MA、Practical in-place merging、Comm. ACM 31 (1988) 348-352

于 2010-07-20T01:16:04.003 に答える
2

これを行うためのアルゴリズムはいくつかありますが、直感的に理解できるものはありません。重要なアイデアは、配列の一部を使用してバッファーとしてマージし、このバッファーを補助スペースとして使用して標準のマージを行うことです。その後、バッファ要素が適切な場所に配置されるように要素を再配置できれば、成功です。

これらのアルゴリズムの 1 つの実装については、私の個人サイトに書いていますので、興味がある方はご覧ください。これは、Huang と Langston による論文「Practical In-Place Merging」に基づいています。おそらく、その論文に目を通し、何らかの洞察を得たいと思うでしょう。

また、これには適切な適応アルゴリズムがあると聞いています。これは、選択した固定サイズのバッファー (必要に応じて O(1) にすることもできます) を使用しますが、バッファー サイズに合わせてエレガントにスケーリングします。頭の中でこれらのどれも知りませんが、「適応マージ」をすばやく検索すると、何かが見つかると確信しています。

于 2010-11-13T23:40:32.260 に答える
1

いいえ、それは不可能ですが、そうであれば私の仕事ははるかに簡単になります:)。

回避できない O(log n) 係数があります。時間または空間として受け取ることを選択できますが、それを回避する唯一の方法は、並べ替えないことです。O(log n) スペースを使用すると、うまく収まらなかった要素を隠した場所を追跡する継続のリストを作成できます。再帰を使用すると、これを O(1) ヒープに収まるようにすることができますが、それは代わりに O(log n) スタック フレームを使用することによってのみ可能です。

これは、1 から 9 までのオッズとイーブンをマージソートする進行状況です。定数空間と線形スワップの双子の制約によって引き起こされる順序の逆転を追跡するために、対数空間アカウンティングがどのように必要であるかに注意してください。

. -
135792468
 . -
135792468
  : .-
125793468
   : .-
123795468
    #.:-
123495768
     :.-
123459768
      .:-
123456798
       .-
123456789

123456789

いくつかのデリケートな境界条件があり、二分探索よりも正しく取得するのがわずかに難しく、この (可能な) 形式であっても、悪い宿題の問題です。しかし、本当に良い頭の体操です。

更新 どうやら私は間違っているようで、O(n) 時間と O(1) スペースを提供するアルゴリズムがあります。私は自分自身を啓発するために論文をダウンロードしましたが、この回答は間違っているとして取り下げました。

于 2010-07-20T02:34:13.053 に答える