0

クイックソートを使用して、ファイル内に存在する 100k 要素をソートしようとしています。私のアルゴリズムは、最初の要素をピボットとして使用する場合にのみ機能します。ピボット要素をプログラムに汎用的にするにはどうすればよいですか?クイックソートを使用してピボット要素を選択する最良の方法ピボット要素はデータに依存していますか、それとも特定のアルゴリズムをリアルタイムで使用していますか?

void quicksort(int *temp,int p,int r)
{
    if(r > p + 1)
    {
        int piv = temp[p];
        int left = p + 1;
        int right = r;
        while(left < right)
        {
            if(temp[left] <= piv)
                left++;
            else
                swap(&temp[left], &temp[--right]);
        }
        swap(&temp[--left], &temp[p]);
        quicksort(temp, p, left);
        quicksort(temp, right, r);
    }
}
4

1 に答える 1

1

ピボット選択の制約は、かなり高速である必要があるということです。一般的なアプローチは、最初の要素を選択する、中間の要素を選択する、またはランダムな要素を選択することです。

ランダム要素を使用するのがおそらく最善です。なぜなら、既に並べ替えられているリストでも高速に並べ替える傾向があるためです (最初の要素を使用すると、並べ替えられたリストではパフォーマンスが非常に低下します。これは、後続の要素がすべてピボットの片側に配置されるためです) ）。

中間要素を使用することも、リストが奇妙な非標準的な順序になっている場合を除き、かなり防弾です。

ランダム選択をお勧めします。

私のアルゴリズムは、最初の要素をピボットとして使用する場合にのみ機能します

あなたがこれを言うとき、あなたのピボットが最初の要素でない場合、誤ってソートされたリストを生成するということですか? 詳しく教えていただけますか？

于 2012-09-07T22:09:08.123 に答える