0

以下を使用して Dobly Linked List を実装しています 。割り当てのバブルソートを使用します。並べ替えとリンク リストについて調査した結果、インデックスを使用してリンク リストをバブル ソートするべきではないことがわかりました。リンク リストにはインデックスが存在しないか、うまく実装するのが面倒だからです。

それで、それを読んで、次のコードを書きましたが、正しい道にいるかどうかはまだわかりません。

ダブル リンク リストを使用したバブル ソートの実装の背後にあるロジックを理解するのに助けが必要です。

また、私が効率的に正しい道を進んでいるかどうか、またはこのコーディング演習の試みが完全に間違っているかどうかについて、ある程度の安心感が必要です。

 //This for loop sorts the smaller part of the bubble sort.
for(int i = 0; i < cars.size() - 1; i++)
    {        //This part creates the second "larger" part of the bubble sort.
        for(int j = i + 1; j < cars.size(); j++)
        {


//Did I do this part correctly?  This is where the swap and sort of the bubble sort        takes //place.
//Obviously, I am using the comparable interface, since I am using the compareTo method.
//

//with the bubblesort, all elements must be greater than zero because for the bubble          //sort, 0 is the smallest element in a set of integers.


            if(cars.get(i).getName().compareTo(cars.get(j).getName()) > 0)
            {
                CarName cari = cars.get(i);
                CarName CarNamej = cars.get(j);
                cars.remove(i);
                cars.add(i, carj);
                cars.remove(j);
                cars.add(j, cari);
                }
            }
        }
    }

これを使用して、メイン メソッドでこのメソッドを出力し、並べ替えられた結果を出力します。

bubbleSort(cars);

私は正しいですか、それともすべてのコードで完全に間違ったことをしましたか?

4

4 に答える 4

0

配列またはベクトルでは、インデックス、つまりアイテムのリスト内の位置を介して格納された変数にアクセスします。

リンクされたリストでは、ある項目から次の項目に移動することで特定の項目に到達します。

コードで使用get(i)しているため、リスト内の位置でインデックスを付けているため、明らかに配列またはベクトルを使用しています。いいえ、残念ながら、あなたは完全に間違った道を進んでいます...

近づくと、コードは次のようになります。

boolean changed = true;
while (changed) {  // keep going until we didn't make any more changes (not
                   // strictly the best condition for bubble sort, but it'll do)

    a = first;                  // grab first element
    b = a.next;                 // grab next element
    changed = false;
    while (b!=last) {           // run through all elements
        if (a.value>b.value) {  // compare the two elements; swap if out of order
            a.prev.next = b;    // update element before a to be followed by b
            b.next.prev = a;    // update element after b to be preceeded by a
            a.prev = b;         // b is now before a
            b.next = a;         // and a is after b
            changed = true;     // we made a change, so we're not done
        } else {
            a = b;              // if we didn't swap them, move to next pair
        }
        b = a.next;             // second half of next pair is next after a
    }
}

これは大まかなアイデアを提供するためのものです。それは決して完全でもバグフリーでもありません。たとえば、リストの一番最初にいる場合は、行のfirst代わりに更新する必要があります...しかし、ねえ...とにかく、誰かに宿題をしてもらいたくない、 右？;)a.preva.prev.next = b

基本的に、双方向にリンクされたリストでは、各要素は次の要素 (a.next) と前の要素 (a.prev) に到達する方法を知っています。バブル ソートは、隣接する要素のみを比較するため、この種のリンク リストのソートに適しています。それ以外の場合は、クイック ソート、マージ ソート、またはそれらの組み合わせの方がはるかに高速ですが、リンク リストでは通常提供されない要素へのインデックス付きアクセスが必要です。

お役に立てれば。

ところで: Youtube には、これらのことをうまく説明しているクールなビデオがたくさんあります。

もう 1 つ深刻な問題: http://www.youtube.com/watch?v=P00xJgWzz2c

そしてもっと変わったもの: http://www.youtube.com/watch?v=lyZQPjUT5B4 (クイックソート用のこれらのものは、はるかに優れた音楽を持っています:)

于 2012-12-03T04:36:48.930 に答える
0

リンクされたリストを配列に変換し、配列をソートしてから、コンテンツをリンクされたリストにコピーしてください。

于 2012-12-03T04:56:19.517 に答える
0

あなたが正しい道を進んでいるようには見えません。インデックスの使用を完全に排除し、代わりにノード参照を使用する必要があります。最初に、要素への参照のみを指定して、リストから要素を削除するコードを開発します。次に、2 つの要素への参照のみを指定して、リスト内の既に要素の直前に要素を挿入するコードを開発します。次に、これら 2 つの方法に基づいて並べ替えアルゴリズムを構築できます。

たとえば、要素を削除する方法は次のとおりです。

void remove(Element element) {
    element.previous().setNext(element.next());
    element.next().setPrevious(element.previous());
}

リストの途中にある要素に対してこのコードが機能する理由を理解するには、双方向にリンクされたリストがどのように機能するかを十分に理解する必要があります。element.previous()リストの表現方法によっては、終了条件 (および/またはelement.next()being )をテストする必要がある場合がありますnull。

于 2012-12-03T04:19:31.143 に答える
0

バブル ソートが通常の配列で機能する方法を考えてみてください。単純なバブル ソートの実装は次のようになります。

   for (int i = array.Length; i > 0; i--)
        {
            for (int j = 0; j < i-1; j++)
            {
                if (array[j] > array[j+1])
                {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1]=tmp;
                }
                DisplayElements(array);
            }
        }

違いは、temp int を使用する代わりに、次と前のノードへの参照をリストに保存する必要があることです。

于 2012-12-03T04:22:12.107 に答える