Shuffling

The opposite of sorting is shuffling, a common task in games. Shuffling means randomizing each element in an array. The trick is that each element must appear in the array once and only once, but in a random position. You can’t go through the array randomizing wildly, because you would end up with duplicate elements.

ShuffleArray uses the same helper object as SortArray. It uses the Swap method but doesn’t need the Compare method.

Sub ShuffleArray(av() As Variant, Optional helper As ISortHelper)
    Dim iFirst As Long, iLast As Long
    If helper Is Nothing Then Set helper = New CSortHelper
    
    iFirst = LBound(av): iLast = UBound(av)
    ‘ Randomize array
    Dim i As Long, v As Variant, iRnd As Long
    For i = iLast To iFirst + 1 Step -1
        ‘ Swap random element with last element
        iRnd = MRandom.Random(iFirst, i)
        helper.Swap av(i), av(iRnd)
    Next
End Sub

The algorithm works by choosing any random element between the first and last elements and exchanging it with the last element, which then is random. Next it finds a random element between the first and the next-to-last elements and exchanges it with the next-to-last element. This process continues until the shuffling is finished.

The Fun ’n Games program, which is discussed in Chapter 6, uses the Shuffle sub to shuffle a deck of cards.