0

これは厄介な問題です。次のように簡単なクイックソートを実装しました..

        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 }; 今、スタックオーバーフローがあります..

どうしたの？なぜこれが機能しないのですか?

4

2 に答える 2

4

アルゴリズムにバグがあります。最も単純な入力リスト { 1, -1 } を考えてみましょう。ロジックをステップ実行しましょう。

  1. 最初にピボット インデックス Count / 2 (1) を選択します。
  2. 次に、インデックス 1 (-1) のピボット要素をarrリストから削除します。
  3. 次に、リスト内の残りの各要素arr(インデックス 0 の 1 のみ) をピボットと比較します。
  4. 1 はピボット (-1) より大きいので、gtリストに追加します。
  5. 次にloe、空のリストをクイックソートします。その並べ替えは空のリストを返します。これを結果セットに追加します。
  6. 次に、ピボット値をgtリストの最後に追加すると、リストgtは { 1, -1 } のようになります。 これは、最初に作成したリストとまったく同じであることに注意してください。
  7. 次に、リストのクイックソートを試みgtます。同じ入力でクイックソートルーチンを呼び出しているため、スタックがオーバーフローするまで、同じ一連のステップが再び発生します。

あなたのロジックのエラーは、ピボットを何も比較せずに gt リストに盲目的に追加することです。それを機能させる方法を理解するのはあなたに任せます。

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

于 2011-12-29T18:43:41.007 に答える
0

デバッガーがない場合は、これを試してください...

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());
            }
        }
于 2011-12-29T18:15:36.310 に答える