-2

配列でクイックソートを使用しようとしていますが、何が間違っているのか完全にはわかりません。順番に私の番号は

-2 0 1 4 7 9 11 12 15

しかし、私は得ています:

0 1 4 7 15 12 11 9 -2

ここに私のパーティションコードがあります:

int partition( int* a, int left, int right)
{
    int pivot, leftPoint, rightPoint, temp;
    pivot = a[left];
    leftPoint = left;
    rightPoint = right + 1;

    while(rightPoint > leftPoint)
    {
        while(a[leftPoint] <= pivot && leftPoint <= right)
            leftPoint ++;
        while(a[rightPoint] > pivot)
            rightPoint --;
        temp = a[leftPoint]; 
        a[leftPoint] = a[rightPoint]; 
        a[rightPoint] = temp;
    }
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    return rightPoint;
}

ここで私のアルゴリズムの何が問題なのかを説明してくれる人はいますか?

編集:これは私の最初の配列です:

7 12 1 -2 0 15 4 11 9

私はクイックソートを次のように呼び出します

quicksort(a, 0, 8);

これは私のクイックソートの実装です:

void quickSort( int a[], int low, int high)
{
   int pivotPoint;
   if(low < high)
   {
       // divide and conquer
        pivotPoint = partition( a, low, high);
        quickSort( a, low, pivotPoint);
        quickSort( a, pivotPoint + 1, high);
   }
}
4

2 に答える 2

1

パーティションの最初の要素をしきい値として使用しているようです。それで

leftPoint = left;
rightPoint = right + 1;

ここにそれを含めます。

temp = a[left];
a[left] = a[rightPoint];
a[rightPoint] = temp;

ここで終わり、パーティションの途中で交換します。最初にしきい値を除外する必要があり、次に配列を超えないようにします。

leftPoint = left+1;
rightPoint = right;

EDITまた、しきい値が次の要素よりも小さいかどうかを確認し、そうでない場合にのみ交換する必要があります。

if(a[left+1] < pivot) {
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    rightPoint = left;
}

または、配列がすでにソートされている場合、パーティションは失敗します。

（編集の終わり）

ちょっとした最適化として

    pivotPoint = partition( a, low, high);
    quickSort( a, low, pivotPoint);
    quickSort( a, pivotPoint + 1, high);

ここで、しきい値を完全に除外できます。

    quickSort( a, low, pivotPoint-1);
于 2014-04-28T16:35:58.573 に答える
0

追加情報があると、問題はほぼ確実に次の点にあります。

rightPoint = right + 1;

のパーティショニング ループに入ると、ピボット値(a, 0, 8)と比較されます。a[9]有効なインデックスはa[0]toであるため、これは悪いニュースですa[8]。

SSCCE (短い自己完結型の正しい例)に変換されたコードは次のとおりです。

#include <stdio.h>
#include <assert.h>

static
int partition(int *a, int left, int right)
{
    int pivot, leftPoint, rightPoint, temp;
    pivot = a[left];
    leftPoint = left;
    rightPoint = right + 1;

    while (rightPoint > leftPoint)
    {
        while (a[leftPoint] <= pivot && leftPoint <= right)
            leftPoint++;
        while (a[rightPoint] > pivot)
            rightPoint--;
        assert(a[leftPoint] != -99 && a[leftPoint] != +99);
        assert(a[rightPoint] != -99 && a[rightPoint] != +99);
        assert(leftPoint >= left && leftPoint <= right);
        assert(rightPoint >= left && rightPoint <= right);
        temp = a[leftPoint];
        a[leftPoint] = a[rightPoint];
        a[rightPoint] = temp;
    }
    temp = a[left];
    a[left] = a[rightPoint];
    a[rightPoint] = temp;
    return rightPoint;
}

static
void quickSort( int a[], int low, int high)
{
    int pivotPoint;
    if (low < high)
    {
        // divide and conquer
        pivotPoint = partition( a, low, high);
        quickSort( a, low, pivotPoint);
        quickSort( a, pivotPoint + 1, high);
    }
}

int main(void)
{
    int aplus[] =
    {
        +99, +99, +99,
        7, 12, 1, -2, 0, 15, 4, 11, 9,
        -99, -99, -99
    };
    int *a = aplus + 3;

    quickSort(a, 0, 8);
    return 0;
}

実行すると、アサーションの 1 つが起動します。

Assertion failed: (a[rightPoint] != -99 && a[rightPoint] != +99),
    function partition, file partn.c, line 19.
于 2014-04-28T16:32:15.723 に答える