7

リンクされたリストをソートするためのインプレースソートアルゴリズムを読んでいます。ウィキペディアによると

多くの場合、マージ ソートはリンク リストのソートに最適な選択です。この状況では、Θ(1)追加のスペースのみを必要とする方法でマージ ソートを実装するのは比較的簡単です。アルゴリズム (クイックソートなど) のパフォーマンスは低く、他のアルゴリズム (ヒープソートなど) は完全に不可能です。

私の知る限り、マージ ソート アルゴリズムはインプレース ソート アルゴリズムではなくO(n)、補助的な最悪の場合のスペースの複雑さがあります。現在、これを考慮して、O(1)補助スペースを使用して単一リンクリストをソートするための適切なアルゴリズムが存在するかどうかを判断できません。

4

2 に答える 2

5

コメントで Fabio A. が指摘したように、マージと分割の次の実装によって暗示される並べ替えアルゴリズムは、実際には、再帰 (またはそれらの明示的な同等物) を管理するために、スタック フレームの形式で O(log n) 余分なスペースを必要とします。O(1)-space アルゴリズムは、まったく異なるボトムアップ アプローチを使用して可能です。

下の項目を各リストの一番上から新しいリストの最後に移動するだけで、新しいリストを作成する O(1) スペース マージ アルゴリズムを次に示します。

struct node {
    WHATEVER_TYPE val;
    struct node* next;
};

node* merge(node* a, node* b) {
    node* out;
    node** p = &out;    // Address of the next pointer that needs to be changed

    while (a && b) {
        if (a->val < b->val) {
            *p = a;
            a = a->next;
        } else {
            *p = b;
            b = b->next;
        }

        // Next loop iter should write to final "next" pointer
        p = &(*p)->next;
    }

    // At least one of the input lists has run out.
    if (a) {
        *p = a;
    } else {
        *p = b;        // Works even if b is NULL
    }

    return out;
}

出力リストに追加される最初の項目を特別なケースにすることで、ポインターからポインターを回避することは可能ですpが、私が行った方法はより明確だと思います。

以下は、単純にリストを同じサイズの 2 つの部分に分割する O(1) 空間分割アルゴリズムです。

node* split(node* in) {
    if (!in) return NULL;    // Have to special-case a zero-length list

    node* half = in;         // Invariant: half != NULL
    while (in) {
        in = in->next;
        if (!in) break;
        half = half->next;
        in = in->next;
    }

    node* rest = half->next;
    half->next = NULL;
    return rest;
}

halfは半分の回数だけ前方に移動されることに注意してくださいin。この関数が戻ると、最初に渡されたリストはin、最初の ceil(n/2) アイテムだけを含むように変更され、戻り値は残りの floor(n/2) アイテムを含むリストになります。

于 2012-06-30T10:10:49.663 に答える
1

これは、オランダ国旗問題の質問に対する私の回答を思い出させてくれます。

これが私が思いついたものであると考えた後、これがうまくいくかどうか見てみましょう. 主な問題は、O(1)余分なスペースでのマージソートのマージステップだと思います。

リンクリストの表現:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^head                      ^tail

このマージ手順で終了します。

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p                ^q       ^tail

マージしたいセグメントの存在pとポインタ。q

tailポインタの後にノードを追加するだけです。末尾*p <= *qに追加する場合。p

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p       ^pp      ^q/qq    ^tail    ^tt

それ以外の場合は、 を追加しqます。

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p       ^pp      ^q       ^qq/tail          ^tt

(リストの末尾を追跡するのqが難しくなります)

今、それらを動かすと、自分がどこにいるかすぐにわからなくなります。ポインターを移動したり、長さを方程式に追加したりする巧妙な方法で、これを打ち負かすことができます。私は間違いなく後者を好みます。アプローチは次のようになります。

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p(2)             ^q(2)    ^tail


[ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p(1)    ^q(2)             ^tail


[ 3 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p(1)    ^q(1)             ^tail


[ 4 ] => [ 1 ] => [ 2 ] => [ 3 ]
  ^p(0)/q(1)                 ^tail


[ 1 ] => [ 2 ] => [ 3 ] => [ 4 ]
  ^q(0)                      ^tail

ここで、O(1)余分なスペースを使用して要素を移動できるようにします。

于 2012-06-30T09:41:38.613 に答える