1

だから私は二重リンクリストに挿入ソートをさせようとしています

現在、ノードを適切な場所に移動するだけで問題が発生しています。比較は機能していますが、ノードが移動しません。

public void insertionSort()
{
    Node temp;
    Node start = this.head.next;
    Node next = start.next;
    Node prev = this.head;

    while(start != this.head)
    {
        if(start.data.compareTo(next.data) > 0) //start is larger than next
        {
            temp = start;
            start = next;
            next = temp;
        }
        start = start.next;
        next = next.next;
        prev = prev.next;
    }
}

誰かがこのアルゴリズムを正しくするのを手伝ってくれるかどうか疑問に思いました。循環二重リンクリストを使用して、時間の複雑さについてさまざまな並べ替えルーチンをテストしています。

4

1 に答える 1

0

楽しいパズル！

あなたのアルゴリズムで私が見ることができる主な問題は、挿入されるノードに1 つ戻る機​​会しか与えないことです。

挿入ソートは、リストの 2 番目のノードから最後のノードまで 1 つずつ検索し、前の既にソートされたリストでソートされるまで逆方向にスワップします。これには数回のスワップが必要になる場合がありますが、アルゴリズムでは 1 つ (if 条件が true の場合) または 0 (false の場合) しか許可されません。たとえば、次のように並べ替えているとします。

紀元前

startが b と c にあるときに挿入ソートが機能し、次に a に移動します。ここで、「a が c の前にある場合、c と交換する」と言って、次のようにします。

バック

...しかし、その後、アルゴリズムは終了します。挿入されるノードごとに実行する必要があるスワップの数は未定であるため、そこに別の while ループが必要です。以下は、挿入ソート アルゴリズムの擬似コードです。

function insertion_sort(items) {
    while (i=1; i < items length; i++) { // for elements 1 to n
        while (j=i; j >= 0; j--) { // look backward through all previously sorted items
            if (items element at j < items element at j-1) {
                 swap element at j with element at j-1
            } else {
                break out of the loop
            }
        }
    }
}
于 2012-10-18T04:55:57.650 に答える