0

二重リンクリストで機能するバブルソートの実装を取得しようとして、これに数時間携わっています。私のコードは1回のパスで機​​能するようですが、ソートを完了せずに途中で終了します。任意のガイダンスをいただければ幸いです。

public void bubbleSort()
{
    Node cur = head.getNext();
    boolean done = false;

    while (!done)
    {
        done = true;
        while(cur != tail)
        {
            if (cur.getNext().getCount()>cur.getCount())
            {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

私が使用しているスワップ方法は、2つのノード間の循環ループになるまで、ノードの配置を破壊しているように見えます。

private void swap(Node n1, Node n2)
{
    Node b1, b2, a1, a2;
    System.out.println("Swapping n1: " + n1 + " with n2: " + n2);
    b1 = n2.getPrev();
    if (b1 == n1) // handle adjacent nodes
        b1 = n2;
    a1 = n2.getNext();

    b2 = n1.getPrev();
    if (b2 == n2) // handle adjacent nodes
        b2 = n1;
    a2 = n1.getNext();

    // swap

    n1.setPrev(b1);
    n1.setNext(a1);

    n2.setPrev(b2);
    n2.setNext(a2);

    b1.setNext(n1);
    a1.setPrev(n1);

    b2.setNext(n2);
    a2.setPrev(n2);
}

ありがとう

4

3 に答える 3

1

私があなたのコードで見た問題：

  • headからではなく、から開始する必要がありhead.getNext()ます。
  • 反復Node curごとに再起動する必要があります。while(!done)

これらの変更により、コードは次のようになります。

public void bubbleSort() {
    boolean done = false;
    while (!done) {
        Node cur = head;
        done = true;
        while(cur != tail) {
            if (cur.getNext().getCount()>cur.getCount()) {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

このコードは、メソッドが問題なく機能することを前提としてswapいます。リストに10000のint値を割り当てint countて、クラスのデータとして使用してテストしました。Node

編集：あなたの質問の編集に基づいて、私はNodeクラスとswap関数を次のように作成しました：

private static class Node {
    int count;
    Node next;
    //getters and setters...
}

//this function just swaps data, no need to swap the nodes prev and next
//(note that yours is an algorithm design issue)
private void swap(Node node1, Node node2) {
    int aux = node1.getCount();
    node1.setCount(node2.getCount());
    node2.setCount(aux);
}

実装で行ったすべての定型コードを実行する必要はありませんswap。

于 2013-02-24T05:46:34.840 に答える
0

cur = head.getNext();リンクリストの実装では、外側のループの先頭に追加することで問題なく機能します。したがって、問題はswapリストのメソッドまたは実装にあります。

bubbleSortあなたの方法によれば、このswap方法はノード自体ではなく、ノードのデータのみを交換します。つまり、の値を交換するだけですcount。そうでない場合は、swap方法が問題です。そうしないと、二重リンクリストの実装に問題が発生します。

于 2013-02-24T03:44:59.543 に答える
0

必ず外側のwhileループの最後に保持する必要がありcur = head.getNext();ます。そうしないと、2回目のパスで、内側のwhileループが完全にスキップされ、実行されます。

バブルソートの実行時間を考慮しましたか？MD.Unicornへの回答で、100未満のリストでは正常に機能しましたが、1000のリストでは機能しないことに気付きました。1000の予想実行時間のリストは、100未満のリストよりも少なくとも100倍遅くなります。終了するのに十分な時間を与えています。

100個のリストを並べ替えるのにどのくらい時間がかかりますか？

于 2013-02-24T05:44:16.810 に答える