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;
}
Here is a live demo
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.
ANSWER: Alex has found the reason. swap(*i, *j) can change the value for the iterator pivot_. This is the reason why it must be a value. The pseudo code in Wikipedia also has a comment behind pivot: The value in the middle of the array. I should have strictly followed that.
NOTE: I wrote a comment in the pseudcode in Wikipedia that pivot must not be a pointer or iterator.
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