Сбой быстрой сортировки с ошибками OOB

У меня есть реализация 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;
}

1

Решение

когда newPivot становится 0 следующий вызов newPivot - 1 с беззнаковым типом переполнится до максимального значения. Проверьте newPivot == 0 после QuickSortPartitioner

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]