4
\$\begingroup\$

I have not used C++ for a while. Could you please tell me if my usage of the <random> module is correct? I am not sure if I need to be creating a new instance of uniform_int_distribution on each recursive call. I am not sure that I should be seeding the generator on each recursive call. I suspect these two actions need to happen somewhere outside but I do not know.

Other improvements are also welcome, of course.

#include <random>
#include <iterator>

using generator = std::mt19937;

template<typename iterator>
void quicksort(iterator fst, iterator lst) {
    if (fst >= lst) {return;}

    generator g(42);

    auto i = fst, j = lst;
    auto rval = std::uniform_int_distribution<>(0, std::distance(i, j));

    auto pivot = *(fst + rval(g));

    while (i <= j) {
        for (; *i < pivot; i++);
        for (; pivot < *j; j--);

        if (i <= j) {
            std::swap(*i++, *j--);
        }
    }
    quicksort(fst, j);
    quicksort(i, lst);
}

template<typename iterator>
void qsort(iterator begin, iterator end) {
    if (begin == end) {return;}
    quicksort(begin, end - 1);
}
\$\endgroup\$
4
\$\begingroup\$

Because you are creating a generator in each iteration with the same seed, the value you get from your distribution will be the same.

So no, this is not the correct way to use the new random subsystem in C++11.

You need to pass in a distribution by reference to quicksort(iteratorm,iterator).

Also personally I don't feel that random numbers should be a part of a sorting algorithm because performance becomes non-deterministic. I would suggest you use one of the other pivot selection strategies.

Also your algorithm requires the use of random access iterators. Might be worth noting.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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