Knuth shuffle

Dec 27, 2017 · 1 minute read

A classic algorithm for shuffling the elements of an array in linear time.

struct Random { 
    static func uniform(range: Range<Int>) -> Int {
        let lower = UInt32(range.lowerBound)
        let upper = UInt32(range.upperBound)
        let random = (arc4random_uniform(upper - lower) + lower)
        return Int(random)
    }
}

func shuffle<T>(array: inout [T]) {
    let n = array.count
    for i in 0..<n {
        let j = Random.uniform(range: i..<n)
        let item = array[j]
        array[j] = array[i]
        array[i] = item
    }
}