Quicksort using uniform_int_distribution to select the pivot

Question

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

• alisianoi: A great Q&A on C++ and sorting: stackoverflow.com/questions/24650626/…

Answer 1

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.