Randomizing an Array

Shuffling a digital deck of cards for online poker, for example, is a practical application of our sorting algorithms.

A simple first pass to accomplish this is to assign a random float to every index in an array and then sort using the random float as the key.

But requiring a sort to do this seems like overkill. And it is. An easier way is to use the Knuth shuffle.

The idea here is similar in some ways to Insertion sort. In Insertion sort we traverse an array from left to right and insert the next card from the right unsorted subarray into the correct position in the left sorted subarray.

In the Knuth shuffle we also traverse from left to right. But here we insert the next card from the right subarray into a random position in the left subarray.

In this way cards in the left subarray are now shuffled. We did it with one pass through the array. Thus it’s a linear time algorithm. And we ensured that all cards have an opportunity to be in a random position.

public func knuthShuffle(a: [Double]) -> [Double] {

    var n = a.count

    var b = a

    for i in stride(from: 0, to: n, by: 1) {

        var random = Int.random(in: 0..<((i > 0) ? i : 1))

        b = exchange(a: b, i: i, j: random)

    }

    return b

}

In my console app, I run the program as follows:

var a2: [Double] = [2.0, 2.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0, 6.0, 6.0, 7.0, 7.0, 8.0, 8.0, 9.0, 9.0, 10.0, 12.0, 12.0, 23.0, 23.0, 54.0, 54.0]

let b = knuthShuffle(a: a2)

print(b)