0

私はクイックソートプログラムを書いています。そのためには、配列を分割する必要があります。パーティショニングは関数によって行われますparitionIt()。次のような配列を分割するコードを書きました。

int partition(int beg,int end,double key)
{
    int pLeft = beg;
    int pRight = end-1;
    while(pLeft<pRight)
    {
        while(array[++pLeft]<key);
        while(array[--pRight]>key);
        if(pLeft<pRight)
            swap(pLeft,pRight);
    }
    swap(pLeft,end-1);
    return pLeft;
}

このブロックは、単独で実行すると正常に動作するようです。ただし、他の関数と一緒に実行すると、間違った答えが生成されるようです。私に与えられた次のコードは、すべての問題を解消しますが、私のコードと大差ないようです。

int partitionIt(int left, int right, double pivot)
{
    int leftMark = left; //right of first elem
    int rightMark = right - 1; //left of pivot
    while(true)
    {
        while( theVect[++leftMark] < pivot ) //find bigger
        ; // (nop)
        while( theVect[--rightMark] > pivot ) //find smaller
        ; // (nop)
        if(leftMark >= rightMark) //if pointers cross,
            break; // partition done
        else //not crossed, so
            swap(leftMark, rightMark); //swap elements
    } //end while(true)
    swap(leftMark, right-1); //restore pivot
    return leftMark; //return pivot location
} //end partitionIt()

ブロックは私のものと似ているようですが、正しい答えを出していますが、私のものはそうではありません。と の違いを教えてpartition()くださいpartitionIt()。

4

2 に答える 2

1

すぐにわかる唯一のことは、 で呼び出された場合、関数の動作が異なることですleft + 1 == right。関数はループに入らず、beg;を返します。本の関数はループに入り、最終的なスワップを実行して戻る前にインクリメント およびデクリメントしleftMarkます。rightMarkleftMark

于 2013-07-30T14:36:40.747 に答える