Sorting & Randomisation Of Array

[alex_read]

Hi all! This ones for anyone whos bored or bloody good with algorithms!

Can anyone guide me on how to realistically shuffle a pack of cards?
i.e. at the moment I have a 1 column array representing a card deck,
with the element entries being Herts1 through to SpadeKing, what's the
speediest / most efficient way best way to go about randomising these
elements please - I've realised that on a normal shuffle, not all the cards
are randomised & some stay together next to each other,
so I'm not using the rnd functions at the moment.

Thanks

[snakeeyes1000]

here is the VB language version. It is very fast and very effective, especially around 100000 iterations. Experiment until you are satisfied with that.

Type Card
     'card stuff goes here
End Type
 
Public Deck(51) as Card
 
Sub InitDeck()
     'assign all 52 cards.
End Sub
 
Sub ShuffleDeck(Iterations as Long)
     Dim lCounter1 as Long, lIndex1 as Long, lIndex2 as Long, tmpBuff as Card
     For lCounter1 = 1 To Iterations Step 1
          lIndex1 = Int(Rnd*52)
          tmpBuff = Deck(lIndex1)
          lIndex2 = Int(Rnd*52)
          'get indexes and backup copy.
          Deck(lIndex1) = Deck(lIndex2)
          Deck(lIndex2) = tmpBuff
          'swap cards
     Next lCounter1
End Sub

[bugzpodder]

i don't 100% understand the code but from my POI the code takes two random integers and swap the cards in these two positions, and does it Iteration times.

now, this does not guarentee every number to be picked and therefore moved with a rather small Iteration (say 52) --- although more likely than not. so i would think that when the program starts the cards are in strict increasing order, like 2-3-4-5-...-J-K-A, you could set Iteration to a rather large number.

I have an alternate method that does guarentee a random sequence of cards. simpily treat it as a hash table. i don't know if you are familiar with the idea or not. instead of real shuffling, you re-generate the cards every time.

so assume you have a array Deck[] whose values are set to 0:

int c=Rnd();

for (int i=0;i<52;i++){
for (int j=(c*CardValue)%52;Deck[j]!=0;j=(j+1)%52);
Deck[i]=CardValue;
}

now even though this method has a complexity of O(n²) but its average case is only O(n)-O(nlogn) -- which is what hash table is all about, fast look up.

[snakeeyes1000]

that's right bugz.

[defending_****ty_code]
Your hash table is very nice. Yes, it works better with more iterations. This is actually intentional, as the more times you shuffle the more random it gets. Basically all my code does is cut a deck a certain number of times. And it is actually more random than you might think.
[/defending_****ty_code]

hash table is probably better, though

[jim mcnamara]

Alex - this is how to shuffle a deck - re-written from ancient code

Public cards(52)  ' or whatever array you use for your deck
limit =52
Loop While limit > 1
  x=Rnd() * limit  + 1
  Swap x,limit
  limit = limit - 1
Loop

Sub Swap(i as integer, j as integer)
    Dim tmp
    tmp = cards(j)
    cards(j)=cards(i)
    cards(i)=tmp
End Sub

[snakeeyes1000]

very nice code jim.. the reason I say this is because it's what I posted

[alex_read]

Thanks for the suggestions guys, much appriciated - helped me out a lot!

[jim mcnamara]

Snakey --

Except what I posted is at least 15 years older than you are -
it's from Knuth's 'Art of Computer Programming' 1968 - the algorithm was published in 1957 - I think.