Re: [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

_______________________________________________
vox-tech mailing list
[EMAIL PROTECTED]
http://lists.lugod.org/mailman/listinfo/vox-tech