@Loki Astari is correct in his comment:
rand()
is well know for its bad distribution. But you are using it correctly. Note: rand() % currentIndexCounter
does not give you a perfect distribution unless currentIndexCounter
is an exact divisor of RAND_MAX
. You may want to look at C++11 random header and the generators provided inside.
Since you're using C++11, you should instead utilize the <random>
library. It includes things such as pseudo-random number generators and random number distributions.
Beyond that, I'll just point out some additional things:
With C++11, you should now be using nullptr
instead of NULL
.
This should be changed in srand()
:
std::srand(std::time(nullptr));
However, as mentioned above, you should not be using this with C++11. But in any situation where you must stay with rand
, the above would be recommended.
With C++11, you should also have access to initializer lists. This will allow you to initialize the vector instead of calling push_back()
multiple times:
std::vector<int> elements { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Also note that your push_back()
was only pushing numbers 1-8 into the vector, despite what your comment said. You've used <
instead of <=
in the loop statement, so the 9 was excluded.
currentIndexCounter
should be of type std::vector<int>::size_type
, which is the return type of size()
(or you can just use auto
). This should've given you compiler warnings as it's a type-mismatch and a possible loss of data. Make sure your compiler warnings are turned up high.
currentIndex
is a misleading name because it's being used with iterators, not indices.
Here, auto
gives currentIndex
the type std::reverse_iterator
from std::rbegin()
. You could simply name this something like iter
. It's okay for iterator names to be short.
In the second for
loop, you just need elements.rend()
, without the - 1
. The iterator will already go through the entire vector and stop at the last reverse element.
The iterator increment should be prefix instead in order to improve performance a bit by avoiding a copy. It's best to do this with all nontrivial types such as iterators.
I've tested this by giving randomIndex
a value greater than elements.size()
, causing an exception to be thrown. Even if std::rand()
or another RNG is guaranteed to give you an intended value, it may be best to handle this properly.
Here's the final version with my own given changes, which I've also ran here. I've also included a concise way of displaying the vector before and after the shuffling.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
// seed the RNG
std::random_device rd;
std::mt19937 mt(rd());
std::vector<int> elements { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "Before: ";
std::copy(elements.cbegin(), elements.cend(),
std::ostream_iterator<int>(std::cout, " "));
auto currentIndexCounter = elements.size();
for (auto iter = elements.rbegin(); iter != elements.rend();
++iter, --currentIndexCounter)
{
// get int distribution with new range
std::uniform_int_distribution<> dis(0, currentIndexCounter);
const int randomIndex = dis(mt);
if (*iter != elements.at(randomIndex))
{
std::swap(elements.at(randomIndex), *iter);
}
}
std::cout << "\nAfter: ";
std::copy(elements.cbegin(), elements.cend(),
std::ostream_iterator<int>(std::cout, " "));
}
Output:
Before: 1 2 3 4 5 6 7 8 9
After: 7 9 3 2 4 5 6 1 8
rand() % currentIndexCounter
does not give you a perfect distribution unlesscurrentIndexCounter
is an exact divisor ofRAND_MAX
. You may want to look at C++11 random header and the generators provided inside. \$\endgroup\$