2

I have this quick sort implementation to sort the characters.

int main(){
char val[] = "dcbeaaae";
    QuickSort(val, 0, length);

    for(int i=0;i<length;i++) //Sorted print
        cout<<val[i];
return 0
}

void QuickSort(char values[], int first, int last)
{
    if(first<last)
    {
        int splitPoint;
        Split(values, first, last, splitPoint);
        QuickSort(values, first, splitPoint-1);
        QuickSort(values, splitPoint+1, last);
    }
}

void Split(char values[], int first, int last, int& splitPoint)
{
    int splitVal = values[first];
    int saveFirst = first;
    bool onCorrectSide;

    first++;
    do
    {
        onCorrectSide = true;
        while(onCorrectSide)
        {
            if(values[first] > splitVal)
                onCorrectSide = false;
            else
            {
                first++;
                onCorrectSide = (first<=last);
            }
        }
        onCorrectSide = (first<=last);
        while(onCorrectSide)
            if(values[last] <= splitVal)
                onCorrectSide = false;
            else
            {
                last--;
                onCorrectSide = (first<=last);
            }

        if(first<last)
        {
            Swap(values[first], values[last]);
            first++;
            last--;
        }
    }while(first<=last);

    splitPoint = last;
    Swap(values[saveFirst], values[splitPoint]);
}

void Swap(char& item1, char& item2)
{
    char temp = item1;
    item1 = item2;
    item2 = temp;
}

However, the output that I get from this is a bit wrong i.e I get an additional space in the starting of these sorted characters. On putting a breakpoint, I saw that at index 0, the element is = 0

Input: aaabcdee
Output: aaabcdee (one additional space before the first a )

Any suggestions what I am missing out here?

4

1 に答える 1

6

lengthは、文字配列内の文字数（NUL文字を除く）であると想定しています。クイックソート関数を次のように呼び出す必要があります。

QuickSort(val, 0, length-1);

関数の最後の引数QuickSortは配列の最後の要素のインデックスであり、長さの文字配列ではlengthこのインデックスはlength - 1です。

関数に渡すlengthことで、NUL文字も並べ替えに参加させ、他の文字よりも小さいため、並べ替えられた配列の先頭に移動し、印刷時に空白として印刷されます。

于 2012-06-08T18:03:14.597 に答える