Is this C implementation of Fisher-Yates shuffle correct?

by

First, you should extract the code for generating a random number that’s equally distributed between 0 (inclusive) and n (exclusive) to a separate function. That’s a nice task of work that you will need elsewhere, too.

Second, I would not call srand inside the shuffle function but depend on the caller on initializing the random number generator. That way you can shuffle a deck more than once in a second.

Third, you should do the test for j > upper_bound before dividing by i + 1. It’s unlikely that i will ever be near RAND_MAX.

static int rand_int(int n) {
  int limit = RAND_MAX - RAND_MAX % n;
  int rnd;

  do {
    rnd = rand();
  } while (rnd >= limit);
  return rnd % n;
}

void shuffle(int *array, int n) {
  int i, j, tmp;

  for (i = n - 1; i > 0; i--) {
    j = rand_int(i + 1);
    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;
  }
}

To check whether this implementation may be correct, you need to ensure that you asked the random number generator for log2(n!) bits of randomness. In other words, the product of all the ns given to the rand_int function must be n!.

More Related Contents:

  1. How many times will “Hello World” be printed?
  2. Error: void value not ignored as it ought be
  3. c program to find average
  4. Improve INSERT-per-second performance of SQLite
  5. What does a type followed by _t (underscore-t) represent?
  6. Why does sizeof(x++) not increment x?
  7. How can I multiply and divide using only bit shifting and adding?
  8. Correct way of passing 2 dimensional array into a function
  9. Why was the switch statement designed to need a break?
  10. Which functions from the standard library must (should) be avoided?
  11. Getting a weird percent sign in printf output in terminal with C
  12. How to enter the value of EOF in the terminal
  13. Addresses of two char pointers to different string literals are same
  14. How to convert ASCII character to CGKeyCode?
  15. Shall I prefer constants over defines?
  16. When does appending an ‘f’ change the value of a floating constant when assigned to a `float`?
  17. Why doesn’t C have unsigned floats?
  18. How to handle realloc when it fails due to memory?
  19. popen() alternative
  20. Printf is not working in C signal handler
  21. How to merge two windows vc static library into one
  22. Overriding C library functions, calling original
  23. Sizeof vs Strlen
  24. Linux/POSIX equivalent for Win32’s CreateEvent, SetEvent, WaitForSingleObject
  25. The difference between asm, asm volatile and clobbering memory
  26. To check the E2BIG error condition in exec
  27. How to check if a pointer is freed already in C?
  28. In C how do I print filename of file that is redirected as input in shell
  29. Output single character in C
  30. Redefining NULL

Leave a Comment