1

インデックスの範囲外エラーで失敗するQuickSortの実装があり、その理由がわかりません。

unsigned long PerformQuickSort(std::vector<unsigned int>& values) {
    unsigned long comparisons = 0;
    QuickSortJoiner(values, 0, values.size() - 1, comparisons);
    return comparisons;
}

void QuickSortJoiner(std::vector<unsigned int>& values, std::size_t first, std::size_t last, unsigned long& comparisons) {

    if(first >= last) return;

    std::size_t pivot = first + (last - first) / 2;
    std::size_t newPivot = QuickSortPartitioner(values, first, last, pivot, comparisons);
    QuickSortJoiner(values, first, newPivot - 1, comparisons);
    QuickSortJoiner(values, newPivot + 1, last, comparisons);

}

std::size_t QuickSortPartitioner(std::vector<unsigned int>& values, std::size_t first, std::size_t last, std::size_t pivot, unsigned long& comparisons) {
    unsigned int value = values[pivot];
    Swap(values[pivot], values[last]);
    std::size_t storeAt = first;
    for(std::size_t i = first; i < last; ++i) {
        ++comparisons;
        if(values[i] < value) {
            Swap(values[i], values[storeAt]);
            ++storeAt;
        }
    }
    Swap(values[storeAt], values[last]);
    return storeAt;
}
4

1 に答える 1

2

0になると、符号なし型を使用したnewPivot次の呼び出しは最大値までオーバーフローします。後でnewPivot - 1確認してくださいnewPivot == 0QuickSortPartitioner

于 2012-10-24T18:18:02.113 に答える