Shuffle an array of int in C with - without while

Question

I want to Shuffle an array of ints, the array is sorted and its size in n, values are 1 - n. I Just want to avoid using a while loop in order to make sure the rand() doesn't give me the same index. the code looks somthin like this:

void shuffleArr(int* arr, size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i < n - 1; ++i)
  {
    while((newIndx = i + rand() % (n - i)) == i);

    swap(i, newIndx, arr);
  }
}

The for loop goes until n-1, so for example in the last run it has 50/50 chance of being equal to i. I want to avoid this idea.

Answer 1

Here is the solution, it involves a little bit of both.

void Shuffle(int[] arr, size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i < n - 2; ++i)
  {
    newIndx = i + rand() % (n - i);
    if(newIndx == i)
    {
      ++newIndx;
    }

    swap(i, newIndx, arr);
  }
}

No need to loop until there is a good (random number != i), cuz it is fixed with the if + increment of newIndx.

Answer 2

If you are searching for a random number in range 1...n but excluding some number m in that range, you can instead get a random number in range 1...(n-1) and for any result >= m add 1 to the value.

If you are looking for an explanation of an algorithm for shuffling a finite list, take a look at Fisher-Yates here: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle