Re: Random sorting
Re: Random sorting
- Subject: Re: Random sorting
- From: Greg Titus <email@hidden>
- Date: Mon, 6 Jan 2003 14:16:03 -0800
On Monday, January 6, 2003, at 01:25 PM, Ben Dougall wrote:
Some years ago I worked on a card game and what we did was not to
shuffle the array but rather pick random values out of the array.
The card-dealing algorithm was:
pick a random number in the range of 0 to the number of cards.
Choose the card in that slot.
take the last card, and put it in the slot you just picked.
The first time, you pick a number from 0 to 51. The next time, you
pick a number from 0 to 50, and so on.
but surely that will allow you to pick the same thing twice, which
isn't what's wanted here?
Nope, it doesn't. You are essentially replacing the one you picked out
with the last element and then decrementing the count of the array. The
item picked is removed.
This is essentially the same as my algorithm posted earlier:
- (void)randomizeOrder
{
int index = [self count];
while (index--)
[self exchangeObjectAtIndex:index withObjectAtIndex:(random() %
(index+1))];
}
The only difference is that Ben is describing doing one step at a time,
while the above does all 52 steps (really N steps) in a loop, leaving
the picked items in the array from back-to-front. Note that this is an
O(N) operation.
i did this in c a little while ago
it went like this - generate two arrays. the first one containing all
the things you want to sort randomly - numbers or strings or whatever,
doesn't matter. generate the second array, the same length as the
first and fill it with random numbers - doesn't matter what the random
range is just so long as the range is substantially larger than the
number of items you've got to sort. then use a sort to sort both
arrays at the same time, and base the sort on the random numbers
array... if that makes sense.
that way you only get each thing once and only once, in a random
order. it's as efficient as the efficiency of the sort you use.
...and the most efficient sort you are going to get is O(N log N),
making this algorithm less efficient than the permute above.
Random sorting was actually one of the first examples given in my
analysis of algorithms class many years ago now, and if I remember
correctly and my prof wasn't wrong, you can't do better than the code
above. (Algorithmically, anyway - you could always do small
optimizations like do the method lookup outside the loop and call the
implementation directly, et cetera.) Just goes to show that all that CS
theory is sometimes actually good for something.
Hope this helps,
- Greg
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.