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:
- Make copy of incoming array to variable arrayCopy (we will remove items from this copy)
- Make new empty array randomArray(we will add new values to this array)
- For each item in copied array
- Generate random index from 0 to arrayCopy length
- Remove item with random index from arrayCopy (when remove we can store removed item)
- Add removed item to randomArray
- 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.
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
