制限付き操作で50000番号のリンクされたリストを2つ並べる

Question

私はこのプロジェクトを学校に持っています：リンクされた50,000の数字と空のリストがあります。私は非常に限られた指示のパネルしか持っていません。 "SA" は、 "SB" リスト1

の最初の2つの要素を交換リスト2

の最初の2つの要素を入れ替え

• "SS" は "SA" であると：それらは1

• 「PB」リストの一番上にリスト2の先頭の要素をプッシュ：リストの先頭要素を押すと同時に

• 「PA」の「SB」回転リスト（第1要素が最後になる）

• "RB"：回転リスト2（第1の最後となる）

• "RR"：リスト2

• "RA" の上に1一度

• "RRA" における "RA" および "RB"：回転リスト1（最後となる第一）

• "RRB"：回転リスト2（最後となる第一）

• 「RRR」：一度

で「RRA」と「RRB」私はCでソートアルゴリズムを実装しており、目標は、命令の最小量でそれを行うことです。 私は非常に単純なアルゴリズムを試してみましたが、最大値が上になるまでリスト1を回転させ、リスト2にすべてが入るまで繰り返しリスト2にプッシュしてからリスト1に戻しましたが、リストをソートすることはできませんでした。妥当な時間内に5kを超える数値を返します

Answer 1

私はクイックソートを使ってこれを行う方法を考え出したと思います。ここにいくつかの疑似コードがあります。

編集：更新され、それはやっているものに集中する擬似コードではなく、不必要な構文

quicksort(int n) 
    if n == 1 return 
    int top_half_len = 0 
    choose a median //it's up to you to determine the best way to do this 
    for 0 to n { //filter all values above the median into list 2 
     if (value > median) { 
      push list 1 top to list 2 //list 2 stores the larger half 
      top_half_len++ 
     } 
     rotate list 1 forward 
    } 

    //reverse the list back to original position 
    rotate list 1 backward (n - top_half_len) times 

    //push larger half onto smaller half 
    push list 2 top to list 1 top_half_len times 

    //recursively call this on the larger half 
    quicksort(top_half_len) 

    //rotate smaller half to front 
    rotate list 1 forward top_half_len times 

    //recursively call this on smaller half 
    quicksort(n - top_half_len) 

    //reverse list back to original position 
    rotate list 1 backward top_half_len times 

は基本的に、それは中央値（小さい方の半分）よりも小さいか等しい部分にリストを分割し、より部分も大きく中央値（より大きな半分）。それから、それはこれらの半分の両方でそれ自身を呼びます。長さが1になると、長さ1のリストがソートされるため、アルゴリズムが実行されます。実際の説明のためのGoogleのクイックソート。

私はこれがうまくいくはずだと思っていますが、私はいくつかの重要なケースを見逃しているかもしれません。盲目的にこれに従わないでください。また、配列を扱っている場合は、特定の再帰深度でクイックソートを停止し、ヒープソート（または最悪の場合のO（n^2）の複雑さを防ぐために何かを使用することをお勧めしますが、ここで何が効率的だろう。 update： Peter Cordesによれば、特定の配列サイズよりも小さくなると、挿入ソートを使用する必要があります（特定の再帰深度でIMOする必要があります）。

明らかに、マージソートはリンクリストのほうが速いです。マージソートを実装するにはこれを変更するのは難しくありません。マージソートはクイックソートに似ています。問題文は比較機能が欠落しているので、私はListBの最初のノードとリスタの最初のノードを比較して返す-1 <ため、= 0にする（リスタ、ListBの）を比較定義し、1 why is merge sort preferred over quick sort for sorting linked lists

Answer 2

より大きいか、またはマージソートに本当に必要なすべては、< =と1のために0です。

また、paまたはpbを実行するときにリストが空であることを示す戻り値もありません。ソースリストが空でなければpaまたはpbを定義し、ソースリストが空の場合（コピーするノードがない場合）は0を返します。

目標が最小の命令であるかどうかは、ソースコード内の命令の数またはソート中に実行された命令の数を参照してください。

- 

コード内の最小の命令数は、正しい位置にlist2にノードを挿入するためにlist1との比較に基づいてlist2をローテーションします。 pbで始まり、list2サイズを1に設定します。次にrbまたはrrbを実行して、list2を次のpbを実行する場所に回転します。このコードは、リスト2を回転させる際の無限ループを避けるために、リスト2の「オフセット」を最小のノードまで追跡します。複雑さはO（n^2）です。

- 

私は最速の並べ替えを考えていると、おそらく実行される命令の最小数は、ボトムアップマージソートです。

循環バッファ/リストのようにリストを回転しながらボトムアップマージソートを行います。シーケンスを使用してノードの数を生成するlist1をlist2にコピー|カウント= 0 | while（pb）{rb |カウント+ = 1}。

カウントを使用して、{pa、rr}、n/2回を使用して、list2からlist1まですべての他のノードを移動します。リストの論理終わりにいつ到達するかを知るためには、各リスト上のノードの実際の数を常に追跡してください。また、各リストのランカウンターを追跡して、ランの論理終点に達したときを知ることができます。この時点で、偶数ノードがlist1上にあり、奇数ノードがlist2上にある2つのリストがあります。

実行サイズは1から始まり、各パスで倍増します。実行サイズが1の最初のパスでは、奇数ノードでも偶数ノードをマージし、サイズが2のソート済みランを作成し、ソートされたノードのペアをlist1とlist2に追加します。たとえば、list1に追加し、list1ノード< = list2ノードを使用する場合は{ra、run1count - = 1}、それ以外の場合は{pa、ra、run2count - = 1}を使用します。実行の終了に達すると、残りの実行の残りをリストの末尾に追加します。次のパスでは、リストから2ノードのソートされた実行をマージし、ソートされた4ノードの実行を各リストに交互に追加します。すべてのノードが1つのリストに終わるまで、8、16、...の実行を続けます。

だからそれだノードをカウントする1つのパス、偶数と奇数のノードを分割する一つのパス、およびはceil（LOG2（N））はマージソートを行うに渡します。リンクされたリスト操作のオーバーヘッドは小さい（回転を取り除いてノードを追加する）ので、全体的なマージはかなり速くなければなりません。

カウントパス上の命令の数が、一方（PB）で還元することができる逆LIST2するLIST1コピーであろう、{= 1 +カウント}。 list2をlist1に吐き出すと、rrrを使ってそれらを逆転させます。

複雑さはO（n log（n））です。