Shuffling function using rand()

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 
#include 
#include 

bool find(const std::vector& vec, int index)
{
    for (int i = 0; i  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


Algorithm

• This algorithm is already provided by the standard library.

std::random_shuffle()

• 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:

• Pick a random value in your container. Swap it with the last element.

• Reduce the size of the elements you consider for swapping by 1.

• 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
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(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;

StackExchange Code Review Q#59554, answer score: 10