I was trying to implement the quick sort algorithm using partitioning technique in C++.
The correct one is as below
template <class ForwardIt>
void quick_sort(ForwardIt first, ForwardIt last) {
if (first == last) return;
auto pivot = *std::next(first, std::distance(first, last) / 2);
using pi = decltype(pivot);
ForwardIt mid1 = myscope::partition(first, last,
[pivot](const pi& em) { return em < pivot;});
ForwardIt mid2 = myscope::partition(mid1, last,
[pivot](const pi &em) { return !(pivot < em); });
quick_sort(first, mid1);
quick_sort(mid2, last);
}
However, I made a little change, which resulted in a wrong output. Below is my modified version.
template <class ForwardIt>
void quick_sort(ForwardIt first, ForwardIt last) {
if (first == last) return;
auto pivot = *std::next(first, std::distance(first, last) / 2);
using pi = decltype(pivot);
ForwardIt mid1 = myscope::partition(first, last,
[pivot](const pi& em) { return em < pivot;});
// ForwardIt mid2 = myscope::partition(mid1, last,
// [pivot](const pi &em) { return !(pivot < em); });
quick_sort(first, mid1);
// quick_sort(mid2, last);
quick_sort(mid1+1, last);
}
So can someone help point out where the crux is.
---EDIT----
namespace myscope {
template <class ForwardIt, class UPredict>
ForwardIt partition(ForwardIt first, ForwardIt last, UPredict p) {
first = std::find_if_not(first, last, p);
if (first == last) return first;
for (ForwardIt i = std::next(first); i != last; ++i) {
if (p(*i)) {
std::iter_swap(i, first);
++first;
}
}
return first;
}
};
