2

同期双方向リンク リストに QuickSort アルゴリズムを実装したいと考えています。関数「パーティション」に左右の境界線を指定すると、左側の低い値が検索され、右側に大きい値が配置されます。これが機能するのは、私のピボット要素が常に最も右側にあり、この手順の後は中央にあるためです。

いつもエンドレス ループになってしまいますが、その理由がわかりません。多分間違ったアボート条件？

彼女の私のコード：

private void quickSortRec(DoublyLinkedList in, ListElement l, ListElement r) {

    ListElement pivot = partition(in, l, r);



    if(pivot!=null && l!=r){
        quickSortRec(in, in.first, pivot.prev);
        quickSortRec(in, pivot.next, in.first.prev);
    }
}


public ListElement partition(DoublyLinkedList in, ListElement l, ListElement r){


    ListElement pivot = r;
    ListElement walker = l;


    if(l!=r){


        while(walker != pivot){

            if(walker.getKey() >= pivot.getKey()){

                System.out.println(walker.getKey());

                if(walker.prev == r){
                    l = walker.next;
                    r = walker;
                }
                else{


                    ListElement h1 = walker.prev;
                    ListElement h2 = walker.next;

                    h1.next = h2;
                    h2.prev = h1;
                    walker.prev = pivot;
                    walker.next = l;
                    pivot.next = walker;
                    l.prev = walker;
                    r = walker;

                }

            }
            walker = walker.next;
        }

        if(l.prev == r)
            in.first = l;

        ListElement p = in.first;
        do{
            System.out.print(p.toString()+" ");
            p = p.next;
        }while(p != in.first);

        System.out.println();



        return pivot;

    }

    return null;
}


}
4

3 に答える 3

1

ちょっと調べてみると、あなたのリストは二重にリンクされているだけでなく、両端で接続されているようです (したがって、リストよりもリングに似ています)。つまり、あなたのリスト (要素を含むA, B, C, D) を反復処理するとしたら、次のようにはなりません。

A -> B -> C -> D -> stop

代わりに

A -> B -> C -> D -> A -> B -> C -> D -> A -> B ..... etc.

それが無限ループを起こしている理由だと思います。

DoublyLinkedListクラスのリストの最後の要素への参照を作成し（例in.last：）、それを使用して最後の要素を取得し、最初と最後の要素をいずれかnullまたは何らかの種類にリンクさせますNullListElement extends ListElement

リングとして保持する必要がある場合でも、リストの最後の要素への参照を追加して、次のように言うことができるようにします。

if(walker == in.last) break; // stop
于 2013-04-30T15:07:36.430 に答える
0

最初の ( )への参照を含むクラスを使用したQuickSortの実装を次に示します。リスト要素にはandおよび参照が含まれます。DoublyLinkedListin.firstListElementkeyprevnext

public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {
    in.first = partition(in.first, in.first.prev);
    return in;
}

private ListElement partition(ListElement first, ListElement pivotElement) {
    ListElement left = first;
    ListElement right = pivotElement;

    while (left != pivotElement) {
        if (left.getKey() > pivotElement.getKey()) {
            ListElement next = left.next;
            if (left == first)
                first = next;
            //Remove currentLeft
            left.prev.next = left.next;
            left.next.prev = left.prev;

            //Connect with element after currentRight
            left.next = right.next;
            right.next.prev = left;

            //Connect with pivotElement
            left.prev = right;
            right.next = left;

            right = left; //Switch right with left, since we just swapped their positions
            left = next;  //Assign left to the next object (from the left part)
        } else {
            left = left.next;
        }
    }
    if (first != pivotElement.prev && first != pivotElement)
        first = partition(first, pivotElement.prev);
    if (pivotElement != right)
        partition(pivotElement.next, right);
    return first;
}

これを書いている時点で、最近の Haswel CPU を搭載したデスクトップ コンピューターでこれを実行すると、次の結果が得られます。

クイックソート:
1.000.000 アイテム : 696ms
8.300.000 アイテム: 8131ms

これは、同じデータ構造のMergeSort実装よりもはるかに遅いことに注意してください。同じデータ構造に対して、同じコンピューターで同じ入力を使用して次のタイミングを取得します。

マージソート:
1.000.000 アイテム : 466ms
8.300.000 アイテム: 5144ms

タイミングは私のハードウェアに固有のものであり、異なる結果が得られる可能性があることに注意してください。

于 2014-01-10T20:36:52.777 に答える