4

単独でリンクされたリストをソートするためのクイックソート機能の実装に取り​​組んでいます。これを達成するには、どのアルゴリズムを使用する必要がありますか? リンクされたリストの場合、配列の通常の O(1) ではなく、比較ごとに最悪の場合の O(N) が必要になります。では、最悪の場合の複雑さはどうなるでしょうか?

要約すると、最適なソート アルゴリズムを実現するには、クイック ソート アルゴリズムにどのような変更を加える必要があり、アルゴリズムの最悪の場合の複雑さはどれくらいになるでしょうか?

ありがとう！

私は以下の実装を持っています:

public static SingleLinkedList quickSort(SingleLinkedList list, SLNode first, SLNode last)
{
    if (first != null && last != null)
    {
        SLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SinlgleLinkedList list, SLNode first, SLNode last)
{

    SLNode p = first ;
    SLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}
4

4 に答える 4

4

リンクされたリストに対してマージソートを実装するのはより自然ですが、クイックソートを非常にうまく行うことができます。以下は、いくつかのアプリケーションで使用した C の 1 つです。

リストではクイックソートを効率的に実行できないというのはよくある誤解です。慎重な実装が必要ですが、これは真実ではありません。

あなたの質問に答えると、リストのクイックソート アルゴリズムは基本的に配列の場合と同じです。ピボットを選択し (以下のコードはリストの先頭を使用します)、ピボットを中心に 2 つのリストに分割し、それらのリストを再帰的に並べ替えて、中間のピボットで結果を追加します。少しわかりにくいのは、並べ替えられた結果の末尾にリストをそのまま追加するためのパラメーターを追加すると、リストを余分に渡すことなく追加操作を実行できることです。基本的なケースでは、このリストを追加する作業は必要ありません。

比較が安価な場合、クイックソートはポインターをいじるのにより多くの時間を費やすため、マージソートは少し速く実行される傾向があることがわかります。ただし、比較にコストがかかる場合は、必要な比較が少なくなるため、クイックソートの実行速度が向上することがよくあります。

が初期リストの先頭である場合NODE *listは、次のように並べ替えることができます

qs(list, NULL, &list);

これがソートコードです。そのチャンクは、すでにソートされたリストの最適化であることに注意してください。このようなケースがまれな場合は、この最適化を削除できます。

void qs(NODE * hd, NODE * tl, NODE ** rtn)
{
    int nlo, nhi;
    NODE *lo, *hi, *q, *p;

    /* Invariant:  Return head sorted with `tl' appended. */
    while (hd != NULL) {

        nlo = nhi = 0;
        lo = hi = NULL;
        q = hd;
        p = hd->next;

        /* Start optimization for O(n) behavior on sorted and reverse-of-sorted lists */
        while (p != NULL && LEQ(p, hd)) {
            hd->next = hi;
            hi = hd;
            ++nhi;
            hd = p;
            p = p->next;
        }

        /* If entire list was ascending, we're done. */
        if (p == NULL) {
            *rtn = hd;
            hd->next = hi;
            q->next = tl;
            return;
        }
        /* End optimization.  Can be deleted if desired. */

        /* Partition and count sizes. */
        while (p != NULL) {
            q = p->next;
            if (LEQ(p, hd)) {
                p->next = lo;
                lo = p;
                ++nlo;
            } else {
                p->next = hi;
                hi = p;
                ++nhi;
            }
            p = q;
        }

        /* Recur to establish invariant for sublists of hd, 
           choosing shortest list first to limit stack. */
        if (nlo < nhi) {
            qs(lo, hd, rtn);
            rtn = &hd->next;
            hd = hi;        /* Eliminated tail-recursive call. */
        } else {
            qs(hi, tl, &hd->next);
            tl = hd;
            hd = lo;        /* Eliminated tail-recursive call. */
        }
    }
    /* Base case of recurrence. Invariant is easy here. */
    *rtn = tl;
}
于 2013-02-11T06:37:02.013 に答える
1

クイックソートを使用しても、O(n*log(n)) の期待される動作を失うことはありません。トリックは簡単です — ノードを配列に入れ、ノードの配列をソートし、それらを正しい順序で再リンクします。

于 2013-02-11T13:57:20.763 に答える