A function that shuffles an array passed as an argument

Question

I'm working on a project at school and I want to create a function that shuffles an array passed as an argument. I tried to create one, but it didn't work as I expected...

In this code, I'm trying to copy the elements of the passed array and set them in random order in a second array. Then, copy them again in the passed array..

This is the source code:

void shufarray(int* array, int b)
{
    int hold[b];  
    int i,k;  
    int randV=0, randHold=0;
    srand(b);  
    for(i=0; i<b; ++i) {      
        hold[rand() % (b-1)] = array[i]; 
        k=0;
        do { 
            if(k==0) { 
                randHold = randV;
                k=-1;
            } //end if
            randV = rand()%(b-1);         
        } while(randHold != randV);//end of do\while stetment 
        hold[randV] = array[i];     
    } //end for  
    for(i=0;i<b;++i) {
        array[i]=hold[i]; 
    } //end for 
} //end shufarray()

And this is the output:

hold[ 0 ] = 8
hold[ 1 ] = 11
hold[ 2 ] = 2
hold[ 3 ] = 15
hold[ 4 ] = 18
hold[ 5 ] = 10
hold[ 6 ] = 11
hold[ 7 ] = 17
hold[ 8 ] = 24
hold[ 9 ] = 21
hold[ 10 ] = 12
hold[ 11 ] = 2
hold[ 12 ] = 15
hold[ 13 ] = 9
hold[ 14 ] = 13
hold[ 15 ] = 1
hold[ 16 ] = 15
hold[ 17 ] = 1
hold[ 18 ] = 22
hold[ 19 ] = 11
hold[ 20 ] = 11
hold[ 21 ] = 18
hold[ 22 ] = 17
hold[ 23 ] = 4
hold[ 24 ] = 7
shuffled_hold[ 0 ] = 7
shuffled_hold[ 1 ] = 32561
shuffled_hold[ 2 ] = 22
shuffled_hold[ 3 ] = 0
shuffled_hold[ 4 ] = 18
shuffled_hold[ 5 ] = 8
shuffled_hold[ 6 ] = -632114865
shuffled_hold[ 7 ] = 32561
shuffled_hold[ 8 ] = -628693440
shuffled_hold[ 9 ] = 11
shuffled_hold[ 10 ] = 15
shuffled_hold[ 11 ] = 18
shuffled_hold[ 12 ] = 1
shuffled_hold[ 13 ] = 13
shuffled_hold[ 14 ] = 15
shuffled_hold[ 15 ] = 12
shuffled_hold[ 16 ] = 17
shuffled_hold[ 17 ] = 0
shuffled_hold[ 18 ] = 4
shuffled_hold[ 19 ] = 17
shuffled_hold[ 20 ] = 7
shuffled_hold[ 21 ] = 0
shuffled_hold[ 22 ] = -1
shuffled_hold[ 23 ] = 0
shuffled_hold[ 24 ] = 0

So I'm trying to understand the principle of this operation, anyone helps me to find what is exactly the problem.. Thanks.

Your shuffling algorithm just doesn't make any sense. You're just randomly copying the elements of `array` to `hold`, sometimes you'll overwrite one you did already, other times you'll leave some elements of `hold` uninitialized. There's not an identifiable problem with your code - the logic just isn't there. — Crowman, Jan 14 '16 at 00:07
Your algorithm seems needlessly complicated (and broken). Search for [“random permutation”](https://en.wikipedia.org/wiki/Random_permutation). — 5gon12eder, Jan 14 '16 at 00:08
You can avoid the temporary array by implementing a [Fisher–Yates_shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm). It's fewer lines of code than what you have, and best of all, it works. — user3386109, Jan 14 '16 at 00:23
FYI, using `srand(b)` will always give you the same permutation based on length. You should use an actual entropy source like `time(NULL)` if you want randomization. — Jason, Jan 14 '16 at 00:27

score 0 · Accepted Answer · edited Jun 20 '20 at 09:12

THE PROBLEM

In the previous code, I thought that the solution is to create an array hold[]that holds randomly copied elements from array[]. than copy elements from hold[] back again to array[].the problems are:

the hold[] is uninitialized

sometimes the program will overwrite an element overwrote already

srand(b) will always give the same permutation based on length

THE SOLUTION

I modify the code at the light of the references that are suggested in comments.

the correct way to do it is to start from the last element array[n-1], swap it with a randomly selected element from the whole array (including the last one). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element. Following is the detailed algorithm:

  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i] .

THE CODE

void shufarray(int* array, int b){
    int i,k=0;
    srand(time(NULL));//set the seed
    /* Starting from the last element and swap one by one.
     * NOTE: i > 0 it's because there's no need to run for the first element */
    for (i = b-1; i > 0; i--){
        int j = rand() % (i+1);
        //swap
        k =  array[i];
        array[i] = array[j];
        array[j] = k;
    }//end for
}//end shufarray()

OUTPUT

hold[ 0 ] = 8
hold[ 1 ] = 11
hold[ 2 ] = 2
hold[ 3 ] = 15
hold[ 4 ] = 18
hold[ 5 ] = 10
hold[ 6 ] = 11
hold[ 7 ] = 17
hold[ 8 ] = 24
hold[ 9 ] = 21
hold[ 10 ] = 12
hold[ 11 ] = 2
hold[ 12 ] = 15
hold[ 13 ] = 9
hold[ 14 ] = 13
hold[ 15 ] = 1
hold[ 16 ] = 15
hold[ 17 ] = 1
hold[ 18 ] = 22
hold[ 19 ] = 11
hold[ 20 ] = 11
hold[ 21 ] = 18
hold[ 22 ] = 17
hold[ 23 ] = 4
hold[ 24 ] = 7
shuffled_hold[ 0 ] = 24
shuffled_hold[ 1 ] = 9
shuffled_hold[ 2 ] = 8
shuffled_hold[ 3 ] = 1
shuffled_hold[ 4 ] = 15
shuffled_hold[ 5 ] = 11
shuffled_hold[ 6 ] = 11
shuffled_hold[ 7 ] = 21
shuffled_hold[ 8 ] = 17
shuffled_hold[ 9 ] = 7
shuffled_hold[ 10 ] = 11
shuffled_hold[ 11 ] = 11
shuffled_hold[ 12 ] = 18
shuffled_hold[ 13 ] = 10
shuffled_hold[ 14 ] = 1
shuffled_hold[ 15 ] = 15
shuffled_hold[ 16 ] = 13
shuffled_hold[ 17 ] = 2
shuffled_hold[ 18 ] = 18
shuffled_hold[ 19 ] = 4
shuffled_hold[ 20 ] = 17
shuffled_hold[ 21 ] = 2
shuffled_hold[ 22 ] = 12
shuffled_hold[ 23 ] = 15
shuffled_hold[ 24 ] = 22

REFERENCES: Fisher–Yates shuffle

`srand(time(NULL));/` should not be called repeatedly in `shufarray()`. Better to call only once in the life of the program - perhaps `main()`. — chux - Reinstate Monica, Jan 14 '16 at 16:46

A function that shuffles an array passed as an argument

1 Answers1