C Function of Fisher-Yates Implementation (Random Shuffling Algorithm)

The following is a random shuffling function in C. This uses the Fisher-Yates algorithm, which guarantees an unbiased shuffle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <stdlib.h>
#include <time.h>
 
void shuffle(int *array, size_t n) {
    if (n > 1) {
        // Seed the random number generator to get different results each time
        srand(time(NULL));
 
        size_t i;
        for (i = 0; i < n - 1; i++) {
            // Generate a random index
            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
 
            // Swap array[i] and array[j]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

#include <stdlib.h>
#include <time.h>

void shuffle(int *array, size_t n) {
    if (n > 1) {
        // Seed the random number generator to get different results each time
        srand(time(NULL));

        size_t i;
        for (i = 0; i < n - 1; i++) {
            // Generate a random index
            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

            // Swap array[i] and array[j]
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

This function operates in-place (it changes the input array instead of returning a new one). The srand(time(NULL)) line is used to seed the random number generator based on the current time, to make sure you get different shuffles each time you run the program. It’s generally a good idea to call this just once, rather than every time you shuffle.

The rand() / (RAND_MAX / (n – i) + 1) line is a way to get a random integer between 0 and n – i inclusive. The + 1 is there to make sure that RAND_MAX is a valid output from rand(), which wouldn’t be the case if we just did rand() / (RAND_MAX / (n – i)).

Finally, we use a simple swap operation to exchange the i-th and j-th elements of the array.

Fisher-Yates Algorithms

• C Function of Fisher-Yates Implementation (Random Shuffling Algorithm)
• Teaching Kids Programming – The Fisher–Yates Random Shuffle Algorithm in Python
• GoLang: Shuffle the Array
• The Fisher–Yates Random Shuffle Algorithm

–EOF (The Ultimate Computing & Technology Blog) —