IComparable <T>は、負の数に使用するとstackoverflowを返しますか？次のように

Question

これはweired問題であり、私はシンプルなクイックソートを実装している。..

 static void Main(string[] args) 
    { 
     List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 }; 
     List<int> sorted = quicksort(unsorted); 
     Console.WriteLine(string.Join(",", sorted)); 
     Console.ReadKey(); 
    } 

    private static List<T> quicksort<T>(List<T> arr) where T : IComparable<T> 
    { 
     List<T> loe = new List<T>(), gt = new List<T>(); 

     if (arr.Count < 2) 
      return arr; 

     int pivot = arr.Count/2; 
     T pivot_val = arr[pivot]; 
     arr.RemoveAt(pivot); 

     foreach (T i in arr) 
     { 
      if (i.CompareTo(pivot_val) <= 0) 
       loe.Add(i); 
      else 
       gt.Add(i); 
     } 

     List<T> resultSet = new List<T>(); 
     resultSet.AddRange(quicksort(loe)); 

     gt.Add(pivot_val); 

     resultSet.AddRange(quicksort(gt)); 
     return resultSet; 
    } 

出力は次のとおりです。1,2,3,4,5,6,7,8,9

しかし、私はソートされていないリスト内の任意の負の数を使用する場合、stackoverflowの誤差がある例 ため

場合は、リストに新しい=未分類リスト{1、3、5、7、9、8、6、4、2、- 1}; 今、スタックオーバーフローが発生しました。

何が起こっているのですか？なぜこれは動作していないのですか？

Answer 1

あなたのアルゴリズムでは、バグがあります。最も簡単な入力リスト{1、-1}を考えてみましょう。あなたのロジックを歩みましょう。

1. は、最初に、ピボットインデックスを選択してください1.
2. あなたはその後arrリストからインデックス1（-1）でピボット要素を削除/ 2をカウント。
3. 次に、arrリスト内の残りの要素（インデックス0に1だけあります）とピボットを比較します。
4. 1はピボット（-1）より大きいので、gtリストに追加します。
5. 次に、loeのリストがクイックソートされています。これは空です。そのソートは空のリストを返します。これを結果セットに追加します。
6. gtリストの末尾にピボット値を追加すると、gtリストは{1、-1}のようになります。 これは、あなたが始めたのとまったく同じリストであることに注意してください。
7. 次に、gtリストをクイックソートしようとします。同じ入力でクイックソートルーチンを呼び出すので、スタックのオーバーフローが発生するまで同じ手順が繰り返されます。

ロジックのエラーは、盲目的にgtリストに何も比較せずにピボットを追加しているようです。私はあなたにそれを動作させる方法を理解するためにそれを残します。

編集する：これは宿題ですが、そうでない場合はList<T>のSort()メソッドに組み込まれている.NETを使用することを強くお勧めします。高度に最適化され、テストされており、自家製品よりも優れた性能を発揮します。なぜ車を再発明するのですか？

Answer 2

デバッガはこれをしようとしていない場合は...

foreach (T i in arr) 
     { 
      if (i.CompareTo(pivot_val) <= 0) 
      { 

       loe.Add(i); 
       Console.WriteLine("loe.add " + i.ToString()); 
      } 
      else 
      { 
       gt.Add(i); 
       Console.WriteLine("gt.add " + i.ToString()); 
      } 
     }