Shuffling function using rand()

Question

I would like to hear your suggestions about my shuffling function in C++. I've decided to take advantage of using rand() to build a shuffling function.

#include <iostream>
#include <vector>
#include <ctime>


bool find(const std::vector<int>& vec, int index)
{
    for (int i = 0; i < vec.size(); ++i){
        if ( index == vec[i] )
            return true;
    }

    return false;
}



void shuffle(int array[], const int size)
{
    int temp[size];
    std::vector<int> indices;

    for ( int i(0); i < size; ++i)
        temp[i] = array[i];

    int index = rand() % size;
    indices.push_back(index);

    for ( int i = 0; i < size; ++i){
        if ( i == 0 )
            array[i] = temp[index];
        else{
              while( find(indices, index) )
                index = rand()%size;

            indices.push_back(index);
            array[i] = temp[index];
        }
    }

}


int main(void)
{
    srand((unsigned int)time(NULL));

    int a[7] = {1,2,3,4,5,6,7};

    for ( int i = 0; i < 7; ++i)
        std::cout << a[i] << " ";
    std::cout << std::endl; 

    shuffle(a, 7);

    for ( int i = 0; i < 7; ++i)
        std::cout << a[i] << " ";
    std::cout << std::endl; 

    return 0;
}

The result:

1 2 3 4 5 6 7 
3 7 1 6 4 5 2 

Answer 1

Algorithm

1. This algorithm is already provided by the standard library.
   std::random_shuffle()
2. If you want to implement it yourself then this is not very optimal (as @rolfl mentioned this is \$O(N^2)\$ at best). @rolfl suggests using Fisher-Yates I call it the Knuth shuffle but basically it is the same thing (and Knuth is a cooler name to throw around :-)

The Knuth shuffle is basically:

1. Pick a random value in your container. Swap it with the last element.
2. Reduce the size of the elements you consider for swapping by 1.
3. if size > 0 goto 1

Rand

The rand algorithm is known to be bad so consider using the new random number generators provided by the standard. If you want to stick to rand() then at least try and use it in a way that does not have bias (or worse bias).

index = rand()%size;

Does not give an even distribution (unless RAND_MAX % size == 0). If the modulus is not zero then a couple options have a slightly higher probability. The correct way to do it is:

// To make sure you have an even distribution you
// must discard all values that contribute to it being uneven.
// So first calculate the max value where we can evenly distribute
// input values [0..max)
//
// If rand() generates a value greater or equal to max then discard it
// as this is part of the unevenness. Otherwise do your modules and return.
int randEven(int max)
{
     maxRange = RAND_MAX / max * max; // Note division is integral
                                      // So result is not necessarily RAND_MAX
     for(;;)
     {
         int r = rand();
         if (r < maxRange)
         {    return r % max;
         }
     }
}

Interface

void shuffle(int array[], const int size);

This is a very C like interface. It also limits you to using C-Arrays (In C++ there are lots of container types). So I would change this to use iterators.

template<typename T>
void shuffle(T begin, T end);

You can still use the same function with your C array (as pointers implement the iterator interface).

shuffle(a, 7);

// becomes

shuffle(&a[0], &a[7]);

Code Review

Try to always use braces.

    for ( int i(0); i < size; ++i)
        temp[i] = array[i];

Its a good habit to get into as there are a few corner cases where it matters and if you just do it by habit you will not hit them.

    for ( int i(0); i < size; ++i) {
        temp[i] = array[i];
    }

Prefer to never use C cast style.

Use a C++ cast. They are easy to spot and the compiler can check most of them for correctness. The dangerous ones are then easy to find during code review.

    srand((unsigned int)time(NULL));

    // The C++ way.
    srand(static_cast<unsigned>(time(nullptr)));

    // Alternatively you can use the constructor syntax (not official name)
    // Personally don't like this.
    srand(unsigned(time(nullptr)));

If you are initializing arrays like this then don't specify a size:

    int a[7] = {1,2,3,4,5,6,7};

    //  Don't say seven
    int a[] = {1,2,3,4,5,6,7};

In this version the compiler calculates the correct size. If you had accidentally used an incorrect size then the compiler can generate incorrect code. If you had used 8 then the compiler fills the array with zeros. If the you had used 6 then you overrun the size of the array. So prefer to let the compiler work it out.

Prefer to use "\n" rather than std::endl. This is because std::endl adds '\n' and then flushes the stream. Unless you really want to flush the stream use "\n". You rarely want to do this as the streams will do it automatically when they fill up.

    std::cout << std::endl; 

Answer 2

Your algorithm is very sub-optimal.

Essentially you take a copy of the input array, then you randomly pick an index values, making sure you have not yet picked that index. Once you have randomly selected the indices, you then copy the data back from the temp copy, back to the input array.

The bottom line is that you loop through the indices once, and, for each time, you check to see whether you have already selected the index. This is a \$O(n^2)\$ operation, with an unlimited down-side..... you could possibly be sitting there forever guessing index values that have already been selected.

This problem has been studied many times, and, by general agreement, the Fisher-Yates shuffle algorithm is about as good as it can get. It is an \$O(n)\$ algorithm (time complexity), and it takes no extra memory space to run (\$O(1)\$).

Do some searches for shuffling, and you will soon arrive here: Fisher-Yates Shuffle.

That algorithm is proven to be optimal, and as reliable as your random number source. Use it, or understand why your algorithm is better/different before you re-invent this particular wheel.

Answer 3

Why are you mixing C-arrays and std::vector? Just stick to the latter, or use any other storage container that does the job. There's especially no need to pass C-arrays around to functions in C++.

You also don't need your own search function when many already exist in <algorithm>. But if you'd rather use your own anyway, then at least replace int with std::vector::size_type to match the return type of size(). It'd be better to use iterators, though. Using for loops with storage containers isn't very idiomatic, and it could be easy to mismatch size types (which you've already done).

Consider returning a sorted container object instead of void, which you might find to be a little nicer. This should also not hurt performance if the compiler takes advantage of Return Value Optimization (RVO) to optimize away this copy.

The output can instead utilize std::copy() and std::ostream_iterator. This is done with just one function call and no loops (making it safer to use). It can be used with containers and C-arrays, although the latter requires C++11 (and you'd be better off using C++11's std::array anyway).

C-array:

std::copy(std::begin(a), std::end(a),
    std::ostream_iterator<int>(std::cout, " "));

Container:

std::copy(a.begin(), a.end(),
    std::ostream_iterator<int>(std::cout, " "));

Overall, this looks very C-like, and std::vector is one of the only C++-like things here. It's okay to experiment with your own algorithms, but at least utilize the non-algorithmic aspects of the STL to help with writing safer and idiomatic C++.

Some misc. things:

• You should also includr <cstdlib> for std::srand() and std::rand().
• C++ doesn't need void parameters; only C does.
• It's not necessary to have return 0 at the end of main(). As success is already implied here, the compiler should do this return for you.

Answer 4

std::random_shuffle is deprecated in C++14

You should use the STL random library and a selected random number generator, like in the code below:

#include <random>

std::random_device rng;
std::mt19937 urng(rng());
std::shuffle( mylist.begin(), mylist.end(), urng);