3
\$\begingroup\$

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));
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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?

\$\endgroup\$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.