リンクリストのクイックソートの実装が配列1よりもずっと遅いのはなぜですか？

Question

リンクリストと配列のクイックソートアルゴリズムの実装が必要なアルゴリズムの問​​題でした。
私は両方の部分を行っています、アルゴリズムは動作していますが、私のクイックソートリンクリストの実装にいくつかのバグがあるようです。

ここは私のクイックソートリンクリストの実装です。ここで

public static void SortLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     if(low != null && low !=high) 
     { 
      DataList.Node p = _PartitionLinkedList(items, low, high); 
      SortLinkedList(items, low, p); 
      SortLinkedList(items, p.Next(), null); 
     } 


    } 

    private static DataList.Node _PartitionLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     DataList.Node pivot = low; 
     DataList.Node i = low; 
     for (DataList.Node j = i.Next(); j != high; j=j.Next()) 
     { 
      if (j.Value().CompareTo(pivot.Value()) <= 0) 
      { 

       items.Swap(i.Next(),j); 
       i = i.Next(); 

      } 
     } 
     items.Swap(pivot, i); 
     return i; 
    } 

クイックソート配列の実装です

public static void SortData(DataArray items, int low, int high) 
    { 
     if (low < high) 
     { 
      int pi = _PartitionData(items, low, high); 
      SortData(items, low, pi - 1); 
      SortData(items, pi + 1, high); 
     } 

    } 
static int _PartitionData(DataArray arr, int low, int high) 
    { 
     double pivot = arr[high]; 
     int i = (low - 1); 
     for (int j = low; j <= high - 1; j++) 
     { 
      if (arr[j].CompareTo(pivot)<=0) 
      { 
       i++; 
       arr.Swap(i,j); 
      } 
     } 
     arr.Swap(i + 1, high); 
     return i + 1; 
    } 

ここでクイックソート配列とリンクリストのパフォーマンスがあります。 （left n、right time）
Picture
qsリンクされたリストからわかるように、6400要素をソートするのに10分かかりました。

また、私はデータ構造のために、私は選択したソートとリンクされたリストと配列の両方のパフォーマンスが同じ構造を使用していたので、それは似ていなかったと思います。

GitHub repo私はいくつかのコードを提供するのを忘れた場合。 Repo

Answer 1

6400要素の場合、10分は非常に長い時間です。通常は、1つではなく、2つまたは3つの恐ろしい間違いが必要になります。

残念ながら、1つの恐ろしい間違いがあります。SortLinkedList(items, p.Next(), null);への2回目の再帰呼び出しは、リストの末尾にあります。あなたはそれがhighに止まることを意味しました。

これは10分を占める可能性がありますが、これはほとんど起こりそうにありません。

また、上記のバグを修正した後でも、並べ替えが正しくないように見えます。出力をテストしてください！

Answer 2

あなたのリンクリスト、特にスワップ方法を調べます。リンクされたリストの実装を見ない限り、私は問題の領域がそこにあると思う。

リンクリストを使用する理由はありますか？彼らはクイックソートn^2lg（n）ソートを行うo（n）検索を持っています。

異なる方法は、リンクリスト内のすべてのアイテムをリストに追加し、そのリストをソートしてリンクリストを再作成することです。 List.Sort（）はクイックソートを使用します。

public static void SortLinkedList(DataList items) 
{ 
    list<object> actualList = new list<object>(); 

    for (DataList.Node j = i.Next(); j != null; j=j.Next()) 
    { 
     list.add(j.Value()); 
    } 

    actualList.Sort(); 

    items.Clear(); 
    for (int i = 0; i < actualList.Count;i++) 
    { 
     items.Add(actualList[i]); 
    } 
} 

Answer 3

リンクリストのクイックソートは通常、配列のクイックソートとわずかに異なります。最初のノードのデータ値をピボット値として使用します。次に、コードは3つのリストを作成します.1つは値<ピボット、1つは値==ピボット、1つは値ピボットです。次に、<ピボットリストと>ピボットリストの再帰呼び出しを行います。再帰呼び出しがこれらの3つのリストを返すとき、コードは3つのリストを連結する必要があるだけです。

リストの連結を高速化するには、最後のノードへのポインタを追跡します。これを簡単にするには、循環リストを使用し、最後のノードへのポインタをリストにアクセスする主な方法として使用します。これにより、（結合）リストの追加が簡単になります（スキャンは行われません）。ある関数の中に入ったら、last-> nextを使ってリストの最初のノードへのポインタを取得します。

最悪の場合のデータパターンの2つは、すでにソートされたデータであるか、すでにソートされた逆のデータです。最後のノードへのポインタを持つ円形リストが使用されている場合、最後のノードと最初のノードの平均を2のメジアンとして使用できます（ノード==ピボットのリストが空になる可能性があります）。

最悪の場合の複雑さはO（n^2）です。最悪のスタック使用量はO（n）です。リスト<ピボットとリスト>ピボットのうちの小さいほうで再帰を使うことで、スタック使用量を減らすことができます。戻った後、ソートされた小さなリストはリスト==ピボットと連結され、4番目のリストに保存されます。その後、ソートプロセスは、残りのソートされていないリストを繰り返し、保存されたリストとマージ（または、おそらく参加）します。

bottom up merge sortを含む任意の方法を使用してリンクリストをソートすると、リンクリストを配列に移動して配列をソートし、ソートされた配列からリンクリストを作成するよりも処理が遅くなります。しかし、私が記述するクイックソート方法は、リンクリストを持つ配列指向アルゴリズムを使用するよりもはるかに高速です。