1

固定ピボットを使用したクイックソートのこのコードを見つけました。指定されたテーブルの右側の要素を常にピボットとして受け取ります。ピボットとしてランダムな要素を取りたい。ここがピボットだと思うxので、与えられたリストからランダムな要素に変更するのがいいと思ったのですが、うまくいかないことがわかりました。

void swap ( int* a, int* b )
{
    int t = *a;
    *a = *b;
    *b = t;
}


int partition (int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);
    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

void quickSortIterative (int arr[], int l, int h)
{
    int stack[ h - l + 1 ]; 
    int top = -1;

    stack[ ++top ] = l;
    stack[ ++top ] = h;

    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];

        int p = partition( arr, l, h );

        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        } 
        if ( p+1 < h )
        {
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
}

ライン変えてみた

int x = arr[h];

と

swap(&arr[i+1], &arr[j]);

に

int r = l+rand()%(h-l);
int x = arr[r];

その後

swap(&arr[i+1], &arr[r]);

しかし、正しくソートされていません。明らかに、私はここで何か間違ったことをしています。助けてください。

4

2 に答える 2

2

パーティション関数は、ピボットがパーティションの最後にあると想定しています。最初にランダム ピボットをパーティションの最後に移動することを検討してください。

すなわち追加

swap(&arr[r], &arr[h]);

ピボットを選択した後。

于 2013-03-20T06:03:05.523 に答える
2

r問題は、「パーティション」関数がピボットを移動するようになったため、インデックスに留まらないことです。また、関数は最後の要素 ( index h) も見逃しています。最も簡単な解決策は、ピボットを選択した直後にピボットを一番右の位置に配置し、他のすべてを同じままにすることです:swap(&arr[r], &arr[h]);の最初のループの前に置きpartition()、最後のスワップをswap (&arr[i + 1], &arr[h]);

于 2013-03-20T06:05:41.550 に答える