0

10から1,000,000の数値をソートするクイックソート関数を作成しようとしています。すべてを繰り返しますが、並べ替えはせず、ベクトルをそのまま出力します。

何らかの理由で、ループから飛び出すのがwhile早すぎます。私が使用しているテスト入力は次のとおりです：（3 6 2 5 1 7 9 10 4 8）。そしてそれは出力です：（1 2 6 5 3 7 9 10 4 8）

int main()
{
    std::cout << "Which file would you like to sort?\n";
    std::cin >> file;

    std::ifstream in(file.c_str());

    // Read all the ints from in:
    std::copy(std::istream_iterator<int>(in), std::istream_iterator<int>(),
            std::back_inserter(numbers));

    int max = numbers.size();
    quickSort(numbers, 0, max-1);

    // Print the vector with tab separators:
    std::copy(numbers.begin(), numbers.end(),
            std::ostream_iterator<int>(std::cout, "\t"));
    std::cout << std::endl;

    return 0;
}


void quickSort(vector<int> &numbers, int start, int end)
{
    int i = start;
    int j = end;
    int pivot=numbers[start];
    int temp;
    while( i != j )
    {
        while( numbers[i] < pivot && i < j)
            i++;
        while( numbers[j] >= pivot && i < j)
            j--;

        temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;

        if( j < start )
        {
            quickSort( numbers, start, j );
        }

        if( i < start )
        {
            quickSort( numbers, i, end);
        }
    }
    return;
}
4

2 に答える 2

3

この行は場違いに見えます：

int pivot=numbers.size()/2;

と位置numbersに関係なく、ベクトルの中央の要素をピボットとして選択します。startend

于 2012-06-26T23:57:22.490 に答える
2

おそらくとりわけ、スワップを見つけるためにインデックスを移動するときに、実際にはベクトルの内容を見ていません。このセクション：

    while( i < pivot && i < j)
        i++;
    while( j >= pivot && i < j)
        j--;

これに変更する必要があります：

    while( numbers[i] < pivot && i < j)
        i++;
    while( numbers[j] >= pivot && i < j)
        j--;

コメント提供者の1人が述べたように、より大きな教訓は、優れたデバッガーを使用してコードをステップ実行する方法を学ぶことです。

同様に、配列値としてピボットを選択する必要があります。例えばpivot = numbers[start]

于 2012-06-27T00:03:36.337 に答える