1

私の一般的な QuickSort アルゴリズムには、原因を特定できない 2 つの問題があります。

  1. リストが正しくソートされないことがあります
  2. 20,000 項目を超えるリストを扱う場合、値が何度も繰り返されるとスタック オーバーフローが発生することがよくあります (これは実際の問題ではないと思います)。

リストが正しくソートされないことはかなりまれであるため、リストは適度に大きくする必要があります。以下の貼り付けは、インストールされているソフトウェアの 172 要素のリストの最初の 13 要素を示しています。最初の列は最初の並べ替え後の出力を示し、2 番目の列は 2 番目の並べ替えの出力を示しています。

Adobe AIR                         7-Zip 4.65 (x64 edition)
7-Zip 4.65 (x64 edition)          Adobe AIR
Adobe Community Help              Adobe Community Help
Adobe Encore CS4 Codecs           Adobe Encore CS4 Codecs
Adobe Media Encoder CS4 Exporter  Adobe Media Encoder CS4 Exporter
Adobe Media Encoder CS4 Importer  Adobe Media Encoder CS4 Importer
Adobe Media Player                Adobe Media Player
Adobe Reader X (10.1.0)           Adobe Reader X (10.1.0)
Adobe Setup                       Adobe Setup
Adobe Setup                       Adobe Setup
Apple Application Support         Adobe Setup
Adobe Setup                       Apple Application Support
Apple Mobile Device Support       Apple Mobile Device Support
...                               ...

ご覧のとおり、最初に並べ替えたときに、いくつかの不適切な動作があり、別の並べ替えを行うことで修正されます。

スタック オーバーフローに関する 2 つ目の問題は、古い Windows イベント ログ リストを並べ替えると発生します。4 週間にまたがる 52,000 の日付を並べ替えると、うまくいきます。しかし、繰り返しが多い 52,000 個の ID 番号を並べ替えると、システムがクラッシュするずっと前に、スタック サイズが 998 アイテムになります。ほとんどが「gupdate」である列で30,000の長いリストをソートした場合にも発生します。

今、私が見る限り、スタック カウントは log2(n) である必要があります。これは、スタックに追加された量が、実行された半分の量に等しいためです。

この効果を助けるためにピボットをランダムにしましたが、大きな違いはありませんでした。

Log2(60000) = 16. スタック オーバーフローには十分ではありません。

これは問題のコードです：

private static void QuickSortFunction<T>(T[] array, int start, int end, Comparer<T> comparer)
{
    if (end - start >= 1)
    {
        int leftPtr, rightPtr, pivot;
        Random random = new Random();
        pivot = random.Next(start, end);
        Swap(array, pivot, start);
        pivot = start;

        leftPtr = start + 1;
        rightPtr = end;

        while (leftPtr < rightPtr)
        {
            while ((comparer.Compare(array[leftPtr], array[pivot])) <= 0 && (leftPtr < rightPtr))
            {
                leftPtr++;
            }

            while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr <= rightPtr))
            {
                rightPtr--;
            }

            if (leftPtr < rightPtr)
            {
                Swap(array, leftPtr, rightPtr);
            }
        }
        Swap(array, pivot, rightPtr);
        pivot = rightPtr;

        QuickSortFunction(array, start, pivot - 1, comparer);
        QuickSortFunction(array, pivot + 1, end, comparer);
    }
}

private static void Swap<T>(T[] array, int pointer1, int pointer2)
{
    T temp = array[pointer1];
    array[pointer1] = array[pointer2];
    array[pointer2] = temp;
}

興味のある人にとっては、これは順不同のグリッチの修正です。基本的に、2 要素の配列が正しくない場合、認識に失敗していました。{E, B} などは、独自のピボットを参照しないため、変更されません。

    if (end - start >= 1)
    {
        int leftPtr, rightPtr, pivot;
        Random random = new Random();
        pivot = random.Next(start, end);
        Swap(array, pivot, start);
        pivot = start;

        leftPtr = start;
        rightPtr = end;

        while (leftPtr < rightPtr)
        {
            while ((comparer.Compare(array[leftPtr], array[pivot])) < 0 && (leftPtr < rightPtr))
            {
                leftPtr++;
            }

            while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr < rightPtr))
            {
                rightPtr--;
            }

            if (leftPtr < rightPtr)
            {
                Swap(array, leftPtr, rightPtr);
            }
        }
        Swap(array, pivot, rightPtr);
        pivot = rightPtr;

        QuickSortFunction(array, start, pivot - 1, comparer);
        QuickSortFunction(array, pivot + 1, end, comparer);
    }

スタック オーバーフローの解決策を書いたら更新します。

4

3 に答える 3

1

今、私が見る限り、スタック カウントは log2(n) である必要があります。これは、スタックに追加された量が行われた半分の量に等しいためです。

これは、入力を同様の1サイズの半分に分割した場合にのみ当てはまります。たとえば、すべての項目が等しいリストを並べ替えると、一方の側に要素がなく、他方の側にピボット以外のすべてが存在する、非常に不均等な分割が発生します。その場合、各レベルは入力サイズを 1 だけ減らすため、O(n)スタック サイズを取得します。

これを回避する 1 つの方法は、ピボットに等しいすべての要素を中央に配置する代わりに、3 方向のパーティショニングを使用することです。

1分割が一定の比率よりも常に優れている場合は、問題ありません。

于 2012-04-28T11:27:37.880 に答える
1

まず、順不同の問題を見てみましょう。大きなループは まで続きleftPtr >= rightPtrます。2 番目のループで がテストされるためleftPtr <= rightPtr、最後の である可能性がleftPtr > rightPtrあります。その場合、(大きなループの後で) ピボットと、「OK」と見なされた要素 (rightPtrによって渡されたものを指します) を交換していますleftPtr。

スタック オーバーフローの問題についてはよくわかりませんが、Hammar の提案は、特に問題が多くの等しい要素の大きなリストで発生すると言ったことから、妥当と思われます。

于 2012-04-28T11:32:33.663 に答える
0

作成した無限ループに注意してください...関数は、その固有の値が使用中に実現されるために終了する必要があります。

于 2013-02-21T19:33:11.797 に答える