I have implemented Quicksort from Wikipedia. The code calculates the middle pivot value of two iterators with ptrdiff_t. But I want to calculate the middle iterator not the value. The following code works. But if pivot_mid() is used it can hang or end with sigsegv.
#include <array> // std::array
#include <cassert> // assert
#include <cstddef> // ptrdiff_t
#include <ctime> // std::time
#include <iostream> // std::cout
#include <iterator> // std::ostream_iterator
template <typename T, typename Compare, typename Partition>
void quicksort_hoare_from_cormen_et_al(T first, T after_last, Compare comp, Partition part) {
// if p < r
if (std::distance(first, after_last) > 1) {
// q = Partition(A,p,r)
T pivot = part(first, after_last, comp);
// Quicksort(A,p,q) // the pivot IS included
quicksort_hoare_from_cormen_et_al(first, pivot 1, comp, part);
assert(std::is_sorted(first, pivot 1, comp));
// Quicksort(A,q 1,r)
quicksort_hoare_from_cormen_et_al(pivot 1, after_last, comp, part);
assert(std::is_sorted(pivot 1, after_last, comp));
}
}
auto pivot_mid = []<typename T>(T first, T after_last) {
return first (after_last - first) / 2;
// return first (std::distance(first, after_last) / 2);
// return first (std::distance(first, std::prev(after_last)) / 2);
// return std::next(first, (std::distance(first, std::prev(after_last)) / 2));
// return std::next(first, std::distance(first,after_last)/2);
};
template<typename T, typename Compare>
T partition_hoare_from_wikipedia(T first, T after_last, Compare comp) {
// pivot := A[floor((hi lo) / 2)]
// auto pivot = pivot_mid(first, after_last); // this is an iterator for the pivot // I WANT THIS
ptrdiff_t right = (after_last - first) - 1;
ptrdiff_t left = 0;
auto pivot = first[left (right - left) / 2]; // this is the value of the pivot
// i := lo - 1
auto i = first - 1;
// j := hi 1
auto j = after_last;
// loop forever
while (true) {
// do i := i 1 while A[i] < pivot
do { i;} while (comp(*i, pivot)); // if pivot is an iterator, then change to *pivot
// do j := j - 1 while A[j] > pivot
do {--j;} while (comp(pivot, *j)); // if pivot is an iterator, then change to *pivot
// if i ≥ j then return j
if (i >= j) return j;
// swap A[i] with A[j]
std::swap(*i, *j);
}
}
template <class T, std::size_t N>
std::ostream& operator<<(std::ostream& o, const std::array<T, N>& arr) {
std::copy(arr.cbegin(), arr.cend(), std::ostream_iterator<T>(o, " "));
return o;
}
int main() {
// std::array<int,5> arr = {5,4,3,2,1};
std::array<int,(1<<2) 1> arr;
std::srand(std::time(nullptr));
std::generate(arr.begin(), arr.end(), [](){return 1 std::rand()/((RAND_MAX 1u)/10);});
std::cout << arr << std::endl;
quicksort_hoare_from_cormen_et_al(arr.begin(), arr.end(), std::less<int>(), [](auto a, auto b, auto c){
return partition_hoare_from_wikipedia(a,b,c);
});
std::cout << arr << std::endl;
return 0;
}
There seems to be a subtle difference between:
ptrdiff_t right = (after_last - first) - 1;
ptrdiff_t left = 0;
auto pivot = first[left (right - left) / 2];
and:
auto pivot_mid = []<typename T>(T first, T after_last) {
return first (after_last - first) / 2;
}
But where is it?
UPDATE #1: I have found something strange. It's possible to get an iterator and a value like this:
auto pivot_ = std::next(first, left (right - left) / 2); // iterator
auto pivot = *pivot_; // value
If we use pivot in the two while loops, then the code runs fine. But with *pivot_ the code hangs. This makes no sense.
CodePudding user response：
These lines:
while (comp_less_or_equal(*j, *pivot, comp)) --j;
// repeat i = i 1 until A[i] >= x
while (comp_less_or_equal(*pivot, *i, comp)) i;
Are missing the necessary boundary checking to prevent i and j going beyond the array boundaries.
In your initial input of 1,2,3,4,5. The second while loop keeps incrementing i after it reaches the 5th element in the list.
But I don't think that's your only bug. I tried putting a quick fix into your code, but it still crashes later. I strongly recommend learning how to use an IDE debugger so you can step through the lines of code to discover where it asserts. Or just get used to adding print/cout statements into your code so you can trace your program's progress. (Basic debugging 101 stuff).
As an aside, here's a pro-tip. Don't inline statements to execute on the same line as the conditional. When you step through in the debugger, it's difficult to tell if the crash occurrend on the comp_less_or_equal statement or on the subsequent i statement.
It's so much easier to debug if you do this:
while (comp_less_or_equal(*j, *pivot, comp)) {
--j;
}
while (comp_less_or_equal(*pivot, *i, comp)) {
i;
}
CodePudding user response：
Update:
After reviewing the behavior of the code under my debugger I've realized the root cause: The inner loops cannot use a pointer to the pivot.
When the array is modified by swapping i and j, the actual value of the element the pivot points to may change. This fundamentally breaks the algorithm, causing the resulting array to be only mostly sorted (like a set of sorted arrays got concatenated instead of merged).
The correct solution is to use the value directly, like so:
template<typename T, typename Compare>
T partition_hoare_from_wikipedia(T first, T after_last, Compare comp)
{
// pivot := A[floor((hi lo) / 2)]
auto pivot = *pivot_mid(first, after_last);
// i := lo - 1
auto i = first;
// j := hi 1
auto j = after_last;
// loop forever
while(true)
{
// do i := i 1 while A[i] < pivot
while(comp(*i, pivot))
{
i;
}
// do j := j - 1 while A[j] > pivot
do
{
--j;
} while(comp(pivot, *j));
// if i ≥ j then return j
if(i >= j) return j;
// swap A[i] with A[j]
std::swap(*i, *j);
}
}
You have two main issues in the code you provided.
First, your midpoint calculation function for iterators is off by one, which causes a stack overflow. Instead of:
auto pivot_mid = []<typename T>(T first, T after_last) {
return first (after_last - first) / 2;
}
This should be:
auto pivot_mid = []<typename T>(T first, T after_last) {
return first ((after_last - first) - 1) / 2;
}
This matches the behavior of your value pivot calculation.
Second, your algorithm fails to account for the possibility that first is already at the head, which will cause the computation of i to underflow the iterator. This crashes your program.
To avoid this, we can adopt slightly different logic for the first increment loop. The original code decremented i, then incremented it again before doing a comparison. We can instead remove the first decrement, and reorder the loop to do the comparison first before the increment so we don't accidentally skip the first element:
// i := lo - 1
auto i = first;
// j := hi 1
auto j = after_last;
// loop forever
while (true)
{
// do i := i 1 while A[i] < pivot
while (comp(*i, *pivot))
{
i;
}
These corrections allow the code to function properly under my debugger (MSVC 2019).
Note that this still does not fully fix your code - while an array of 5 elements works fine for this system, if you extend the number of elements out, the algorithm as written fails to sort the array. Even with as few as ten elements the array would sometimes fail to sort properly.
You will need to pick apart the algorithm as it runs to identify the issue with the sorting. I recommend the following sequence:
9, 7, 2, 4, 2, 4, 10, 7, 7, 4
This will fail to sort when your algorithm is run on it, producing the "sorted" array of:
2, 2, 4, 7, 4, 4, 9, 7, 7, 10