I made a quicksort implementation based on this code. Please review my C++ version.
template<typename I>
I partition(I low, I high) {
auto p = *low;
I i = low, j = high+1;
while (true) {
while (*(++i) < p) { }
while (p < *(--j)) { }
if (i >= j) {
break;
}
std::swap(*i, *j);
}
std::swap(*low, *j);
return j;
}
template<typename C, typename I>
void sort(C& c, I low, I high) {
auto h = high == std::end(c) ? high-1 : high;
if (h <= low) {
return;
}
std::swap(*h, *(std::max_element(low, h)));
I p = partition(low,h);
sort(c, low, p-1);
sort(c, p+1,h);
}
template<typename C>
void sort(C& c) {
if (c.size() == 0) {
throw std::out_of_range("no size");
}
std::random_shuffle(std::begin(c), std::end(c));
sort(c, std::begin(c), std::end(c));
}
