How to shuffle an array in Swift

Given a task - write a function for shuffle array. Let's start from simple solution. This method called Pencil and paper method

Example of function which shuffle array

import Foundation

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

func shuffle(array: [Int]) -> [Int] {
    var arrayCopy = array
    var randomArray = [Int]()
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(arrayCopy.count)))
        let removedValue = arrayCopy.remove(at: randomIndex)
        randomArray.append(removedValue)
    }
    return randomArray
}

let shuffledArray = shuffle(array: array)
print(array) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(shuffledArray) //[7, 6, 9, 2, 8, 4, 3, 1, 5, 10]

Function shuffle, that provided below, works by following algorithm:

1. Make copy of incoming array to variable arrayCopy (we will remove items from this copy)
2. Make new empty array randomArray(we will add new values to this array)
3. For each item in copied array
1. Generate random index from 0 to arrayCopy length
2. Remove item with random index from arrayCopy (when remove we can store removed item)
3. Add removed item to randomArray
4. Return randomArray

Making Extension for shuffle array

For more handy usage let's move this code to extension

Example of extension for shuffle array

extension Array {
    
    func shuffle() -> [Element] {
        var arrayCopy = self
        var result = [Element]()
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(arrayCopy.count)))
            let removedItem = arrayCopy.remove(at: randomIndex)
            result.append(removedItem)
        }
        return result
    }
}

let array2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array2) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array2.shuffle()) //[5, 9, 6, 10, 2, 7, 1, 3, 8, 4]

let strings = ["one", "two", "three", "four", "five"]
print(strings) //["one", "two", "three", "four", "five"]
print(strings.shuffle()) //["five", "four", "one", "three", "two"]

The algorithm remains the same. But for now, because we use extension, any array can be shuffled, as we can see above now we can shuffle array of strings too.

Mutating self extension method
We can add modified version of our extension which modify current array in-place without return new array.

Example of extension which shuffle current array in-place

extension Array {
    
    mutating func shuffleInline() {
        var result = [Element]()
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(self.count)))
            let removedItem = self.remove(at: randomIndex)
            result.append(removedItem)
        }
        self = result
    }
}

var array3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array3) //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
array3.shuffleInline()
print(array3) //[3, 1, 4, 6, 2, 5, 9, 10, 7, 8]

Complexity of Pencil and paper algorithm

Complexity of this algorithm will be O(nˆ2) because

• O(n) is for one 'for loop'
• O(n) is for removing from array

Model Shuffle Algorithm

How we can improve time complexity of shuffling? There is Modern method which allow us to get linear O(n) complexity. It is because we have only one loop over the array and swap random item on each iteration.

Example of shuffle function implemented modern algorithm 

func shuffleModern(array: [Int]) -> [Int] {
    var length = array.count
    var arrayCopy = array
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(length)))
        if length - 1 != randomIndex {
            arrayCopy.swapAt(length - 1, randomIndex)
        }
        length -= 1
    }
    return arrayCopy
}

let array4 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array4) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(shuffleModern(array: array4)) //[9, 6, 7, 10, 2, 8, 1, 4, 3, 5]

Generic function
We also can make our function generic and apply it to array of any type, for example for array of strings.

Example of generic implementation

func shuffleModern<T>(array: [T]) -> [T] {
    var length = array.count
    var arrayCopy = array
    for _ in array {
        let randomIndex = Int(arc4random_uniform(UInt32(length)))
        if length - 1 != randomIndex {
            arrayCopy.swapAt(length - 1, randomIndex)
        }
        length -= 1
    }
    return arrayCopy
}

let strings2 = ["one", "two", "three", "four", "five"]
print(strings2) //["one", "two", "three", "four", "five"]
print(shuffleModern(array: strings2)) //["five", "four", "one", "three", "two"]

Also let's create two extensions as before: 1) will return new shuffled array 2) will shuffle array in-place

Example of extension with modern shuffle algorithm (Immutable and In-place)

extension Array {
    
    func shuffleModern() -> [Element] {
        var arrayCopy = self
        var length = arrayCopy.count
        for _ in arrayCopy {
            let randomIndex = Int(arc4random_uniform(UInt32(length)))
            if length - 1 != randomIndex {
                arrayCopy.swapAt(length - 1, randomIndex)
            }
            length -= 1
        }
        return arrayCopy
    }
    
    mutating func shuffleModernInline() {
        var length = self.count
        for _ in self {
            let randomIndex = Int(arc4random_uniform(UInt32(length)))
            if length - 1 != randomIndex {
                swapAt(length - 1, randomIndex)
            }
            length -= 1
        }
    }
}

var array5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array5) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array5.shuffleModern()) // [2, 6, 10, 5, 4, 7, 3, 8, 9, 1]
array5.shuffleModernInline()
print(array5) // [10, 6, 2, 3, 1, 8, 5, 4, 7, 9]

Source Code

Source code for this post could be found here on GitHub