# Quicksort function

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));
}


This line is funky:

auto h = high == std::end(c) ? high-1 : high;


So on first call you are using one past the end. But on all other situations high is the actual end. The idiom in C++ is to use one past the end. So prefer to stick with standard conventions and use one past the end for high in all situations. This simplifies a lot of your code.

This is definitely wrong:

 std::swap(*h, *(std::max_element(low, h)));


You are putting the largest element at the beginning. The result is that the partition does not work optimal (you basically are always getting the worst case scenario thus converting an O(n.ln(n)) algorithm into O(n^2) algorithm).

### Minor things:

One variable per line.

    I i = low;
I j = high + 1;


When you partition the data put all values of the partition data on one side.

    while (*(++i) < p) { }
while (p < *(--j)) { }


What happens to data that equals p?

• Do you mind reviewing my updated code? I'm extremely unsure about my iterators. Thanks codereview.stackexchange.com/questions/75561/… Commented Jan 3, 2015 at 15:18
• @morbidCode: Already looking. Commented Jan 3, 2015 at 16:29