l i n u x - u s e r s - g r o u p - o f - d a v i s
L U G O D
 
Next Meeting:
October 7: Social gathering
Next Installfest:
TBD
Latest News:
Aug. 18: Discounts to "Velocity" in NY; come to tonight's "Photography" talk
Page last updated:
2002 Nov 25 15:57

The following is an archive of a post made to our 'vox-tech mailing list' by one of its subscribers.

Report this post as spam:

(Enter your email address)
Re: [vox-tech] shuffling arrays in C?
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [vox-tech] shuffling arrays in C?




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
vox-tech@lists.lugod.org
http://lists.lugod.org/mailman/listinfo/vox-tech



LinkedIn
LUGOD Group on LinkedIn
Sign up for LUGOD event announcements
Your email address:
facebook
LUGOD Group on Facebook
'Like' LUGOD on Facebook:

Hosting provided by:
Sunset Systems
Sunset Systems offers preconfigured Linux systems, remote system administration and custom software development.

LUGOD: Linux Users' Group of Davis
PO Box 2082, Davis, CA 95617
Contact Us

LUGOD is a 501(c)7 non-profit organization
based in Davis, California
and serving the Sacramento area.
"Linux" is a trademark of Linus Torvalds.

Sponsored in part by:
Appahost Applications
For a significant contribution towards our projector, and a generous donation to allow us to continue meeting at the Davis Library.