[vox-tech] shuffling arrays in C?

[Micah Cowan]

On Monday, November 25, 2002, at 11:21  AM, Bill Kendrick wrote:

> That 'do...while' loop will get slower and slower and slower until its
> painful, once you're down to the last few elements.  But, on fast 
> machines
> with a small array, it ain't so bad. :^)

If it's possible for your scheme, I'd probably prefer a linked list - 
they are easier to swap and to shuffle.

> Another way to do it is to literally shuffle things.  The example
> below is more like taking cards out two at a time and swapping them.
> (Well, that's literally what's going on with the array :^) )
>
>
>   int i;
>   int index_1, index_2;
>   YOUR_STRUCT * temp_for_swap;
>
>
>   /* Shuffle for a while... */
>
>   for (i = 0; i < SOME_SUITABLY_LARGE_NUMBER; i++)
>   {
>     index_1 = rand() % N;
>     index_2 = rand() % N;
>
>     temp_for_swap = your_array[index_1];
>     your_array[index_1] = your_array[index_2];
>     your_array[index_2] = temp_for_swap;
>   }
>
>
> This is pretty simple.  There's probably more elegant ways of doing
> the swap, too.  Oh, and that doesn't test for if index_1 == index_2
> (e.g., it swaps with itself), but hey, that doesn't matter.
> It's probably minisculy faster for not doing that comparison every
> iteration.

Yeah, but no matter how long you run, there's no way to be sure that a 
significant number of cards were left as-is (which of course is true of 
regular card-shuffling, too). But we can do a little better than real 
shuffling; the method below is similar to how selection sorts work:

   int i;
   int j;
   YOUR_STRUCT *temp_for_swap;

   #define ELEMS_IN_ARY(a) (sizeof (a) / sizeof *(a))

   for (i = 0; i != ELEMS_IN_ARY(your_array); ++i)
   {
      const int selection_size = ELEMS_IN_ARY(your_array) - (i + 1);
      int selected_card = (i + 1)  /* don't include the already selected
                                      cards, or the card to swap with */
          + (int)((selection_size*1.0*rand())/(RAND_MAX+1.0)) /* see 
rand(3) */

      temp_for_swap = your_array[i];
      your_array[i] = your_array[j];
      your_array[j] = temp_for_swap;
   }

The above is, of course, untested code...

-Micah