insertion - 片方向リストの挿入ソート

Question

単一リンクリストで挿入ソートを実行することはできないと考えているのは正しいですか?

insertion sort私の推論:定義上、外側のループで右に移動すると、内側のループで左に移動し、必要に応じて値を上 (右) にシフトし、現在の値を挿入することを意味すると仮定します。内側のループ。その結果、SLL はそのようなアルゴリズムに対応できません。正しい？

Answer 1

これが私のコードです。お役に立てば幸いです。

int insertSort(Node **pHead)
{
Node *current1 = (*pHead)->next;
Node *pre1 =*pHead;
Node *current2= *pHead;
Node *pre2=*pHead;
while(NULL!=current1)
    {
    pre2=*pHead;
    current2=*pHead;

    while((current2->data < current1->data))
    {
        pre2 = current2;
        current2 = current2->next;
    }
    if(current2 != current1)
    {
        pre1->next=current1->next;
        if(current2==*pHead)
        {
            current1->next=*pHead;
            *pHead = current1;
        }
        else
        {
            pre2->next = current1;
            current1->next = current2;
        }
        current1 = pre1->next;
    }
    else
    {
        pre1 = pre1->next;
        current1 = current1->next;
    }
}
return 0;

}

Answer 2

まあ、私は明白な船長のように聞こえますが、答えはほとんどの場合、要素がリンクされているのと同じ方法ですべての反復を維持し、定義に従って適切な並べ替えアルゴリズムを実装しても問題ないかどうかに依存します。挿入ソートの定義を台無しにしたくないので、本当に自分で考えなければならないのではないかと思います。少なくともしばらくの間。とにかく宿題です... ;)

わかりました、これが私がページを閉じる直前に得たものです。SLL を逆方向に繰り返すことはできますが、n 個の要素すべてにアクセスするには n*n/2 回のトラバーサルが必要になります。したがって、理論的には、並べ替えループの走査方向は問題ありません。それはあなたの質問をかなり解決すると思います。