How To: Shuffling An Array In Swift Explained
Algorithms are fun! In this article, you’ll learn how to shuffle an array of strings in Swift.
Learning how to efficiently shuffle arrays is a good entry point to learn more about computer algorithms and complexity. You’ll want to understand how efficient an algorithm is and how you can make an algorithm faster.
You might not need to shuffle arrays in every one of your app projects, but algorithms definitely come into play in many of your apps. Understanding how algorithms run efficiently is a mustknow if you’re looking for a job as a professional developer.
If you’ve come here hoping for a quick fix, you’re out of luck! Instead of handing you a Swift snippet to shuffle an array, we’re going to dive a bit deeper and figure out how a shuffling algorithm actually works.
Here’s what you’ll learn:
 How to approach making an algorithm to shuffle an array, and how to go from “doing it yourself” to designing an efficient algorithm
 How to express the “complexity” of an algorithm with Big O Notation
 How to shuffle an array of strings in Swift in O(n) time without using extra memory space…
Shuffling is one of many algorithms you come across when developing iOS apps. Hopefully, when you come across an algorithm problem in the future, after reading this article, you know how to tackle it…
Ready? Let’s go.
 The FisherYates Shuffle Algorithm
 Algorithm Complexity With Big O Notation
 Shuffling An Array Of Strings In O(n) Time
 Further Reading
Quick Note: If you came here just for the code snippet, scroll down…
The FisherYates Shuffle Algorithm
Before you start Googling for a shuffle algorithm in Swift, think for a second how you would perform such a shuffle yourself.
A crucial step in implementing an algorithm is to imagine doing the task yourself. By assessing the steps in the algorithm, you ultimately understand it better. There’s nothing worse than building an app from random pieces you found on the internet that you don’t understand!
So… how do you shuffle an array of strings yourself?
Let’s imagine you’re organising a raffle. Every participant gets a numbered ticket and then a random number is pulled from a box containing a copy of every number. The person with the random ticket wins a prize!
You could do the same thing to shuffle an array:
 Put all the array items in a container
 Pull one random item out of the container
 Place the item on a table
 Pull another random item out
 Place it next to the previous item
 Continue until the container is empty
(Don’t do this at a raffle. People will look at you funny…)
You’re changing the order of the array by pulling out random items and putting them in a new order. That’s shuffling!
Here’s how that looks in Swift:
var items = ["A", "B", "C", "D", "E", "F", "G", "H"]
var shuffled = [String]();
for i in 0..<items.count
{
let rand = Int(arc4random_uniform(UInt32(items.count)))
shuffled.append(items[rand])
items.remove(at: rand)
}
print(shuffled)
In the above example code, this happens:
 First, create two arrays
items
andshuffled
. Theitems
array contains an ordered sequence of the characters A to H. Theshuffled
array is empty.  Then, loop from
0
to7
, i.e. loop 8 times: once for all the times in theitems
array. For every iteration, do this: Pick a random index number between
0
anditems.count
(noninclusive).  Get item for that index from
items
and append it to theshuffled
array.  Remove the item from
items
to avoid picking the same number twice.
 Pick a random index number between
 Finally, print out the
shuffled
array.
This isn’t the most efficient approach to shuffle an array, though!
A better algorithm that uses a similar approach to shuffle an array is the FisherYates shuffle algorithm. This algorithm has a penandpaper approach and a modern approach. The modern approach is more efficient, but let’s first look at the penandpaper approach.
It’s surprisingly simple. You pick a random number from the sequence, strike it out, and write the number on a separate piece of paper.
 Write down a set of numbers between 1 and
N
. This is the sequence of numbers you want to shuffle.  Pick a random number
k
between 1 and the number of “unstruck” numbers remaining.  Counting from the start of the sequence, strike out the kth number not yet struck out, and write it down at the end of a separate list.
 Repeat from step 2 until all numbers have been struck out.
The resulting list is now shuffled!
When counting out to k
, make sure to only count the unstruck numbers. By choosing only from the unstruck numbers you avoid choosing the same number twice. You’ll have to make sure that k
lies between 1
and the number of unstruck remaining numbers.
Check out this animation:
Quick Tip: You’ll find that k
starts at the total number of items, like 8
, and steps down by 1
until it reaches 1
. You’ll see the same in the next implementations in this article.
Get complementary access to my course, Zero to App Store, and learn how you can build a realtime chat app with Firebase and Swift!
Algorithm Complexity With Big O Notation
When you’re designing an algorithm you want it to be as efficient as possible. It’s pointless to waste computer resources, right?
The efficiency of computer algorithms comes into play when you’re working with large data sets. What if you need to shuffle an array of a million strings? You’ll want a fast algorithm to do that…
What about everyday apps? Most apps don’t work with large datasets on the frontend, right? Algorithm complexity matters here, too. When you want to quickly perform a task while your app’s user interface updates, to keep it snappy. You might need to push an intensive task to the background, because performing it on the main thread is too intensive and locks up your app. You can only optimize these realworld scenarios if you understand the fundamentals.
Computer programmers use a special mathematical notation to express the complexity of algorithms. It’s called Big O Notation and it’s pretty awesome.
With Big O Notation you express the time it takes for an algorithm to complete. You don’t do this in seconds, like “It takes 10 seconds for the algorithm to finish”, but instead you express the complexity of the algorithm relative to the size of the input.
Let’s say you have an algorithm that takes n
inputs, like shuffling an array of n
items.
 When the complexity is O(1), the time it takes the algorithm to complete is constant, so regardless of the amount of inputs, the time it takes to complete is always the same.
 When the complexity is O(n), the time it takes the algorithm to complete is linear, so the more items you put in, the longer it takes to complete.
 When the complexity is O(n^{2}), the time it takes to complete is quadratic, so if you put twice the amount of items in, you have to do four times the amount of work!
You can see that a complexity of O(1) is better than O(n), and O(n) is better than O(n^{2}).
Quick Note: More efficient, not necessarily faster. An algorithm with O(n) complexity can take more time to complete than another algorithm with O(n^{2}) complexity. Remember that Big O Notation only looks at the time it takes for an algorithm to complete relative to the size of the input.
So… what’s the time complexity of the FisherYates algorithm? It’s O(n^{2}).
Intuitively, you’d say that its complexity is linear: O(n). After all, you do more work to shuffle more items. So why quadratic time complexity?
It’s because of step 3 in the algorithm: you have to count out the kth number not yet struck out. This step adds complexity to the algorithm, because you have to count from the beginning of the array to item k every time you pick a random item from the array.
You can see it as two nested forloops. The outer loop iterates randomly over each item of the array until all items have been selected, and the inner loop counts out each of the remaining items to select the kth item. The larger the input, the more items you have to randomly select, and the more items you have to count out.
Algorithms also have another cost: space…
You can also use Big O Notation to express the amount of memory a computer algorithm needs to complete, compared to the size of the input. This is called space complexity. It’s always expressed as additional space, so the original input for the algorithm isn’t counted.
In the example of FisherYates above you can see that the algorithm needs twice the amount of space compared to the array you put in. You duplicate the original array, by creating the shuffled array, so you need twice the amount of space.
If the original array has 10 items, you need space for 2 x 10 items to complete the shuffle. In Big O Notation, that’s O(n) of additional space.
Ultimately, when designing an algorithm you want to strike a balance between time and space complexity. There’s often a tradeoff between the two. You also want to optimize your code for readability and maintainability. It’s not always smartest to create a super fast algorithm that’s hard to read and maintain.
Quick Note: Are you learning how to code iOS apps? Check out Zero to App Store, the iOS development course I created. The courses are extremely practical, but don’t skimp on fundamental topics you simply need to know.
» Learn more about Zero to App Store
Shuffling An Array Of Strings In O(n) Time
What can you do to improve the efficiency of the FisherYates algorithm to shuffle an array?
First, let’s figure out what needs to happen to improve efficiency:
 The time complexity needs to go from O(n^{2}) to O(n)
 The space complexity needs to go from O(n) to O(1)
In other words, you only want to iterate the array once, to reduce time, and you don’t want to duplicate the input, to reduce space.
The solution is surprisingly simple. Instead of generating a new array, you’ll shuffle the array inplace. This ensures that you wont use any extra space.
To achieve an inplace shuffle, you need to take a random item from the array and swap it with the last item in the array.
While you move through the array, the shuffled items end up near the end of the array. You avoid picking items that have already been shuffled, i.e. items from the end of the array, by using a counter.
Here’s a simple Swift implementation:
var items = ["A", "B", "C", "D", "E", "F", "G", "H"]
var last = items.count  1
while(last > 0)
{
let rand = Int(arc4random_uniform(UInt32(last)))
print("swap items[\(last)] = \(items[last]) with items[\(rand)] = \(items[rand])")
items.swapAt(last, rand)
print(items)
last = 1
}
In the above example, this happens:
 First, define an array
items
and take the index for the last item (items.count  1
) and then assign it tolast
.  Then, while
last
is greater than0
: Take a random index from the array between
0
andlast
(noninclusive)  Print out the swap that’s taking place, to see what’s going on
 Swap the last item with the random item with the
swapAt(_:_:)
function  Print the result
 Decrease last with
1
 Take a random index from the array between
Here’s the output:
swap items[7] = H with items[2] = C
["A", "B", "H", "D", "E", "F", "G", "C"]
swap items[6] = G with items[4] = E
["A", "B", "H", "D", "G", "F", "E", "C"]
swap items[5] = F with items[2] = H
["A", "B", "F", "D", "G", "H", "E", "C"]
swap items[4] = G with items[2] = F
["A", "B", "G", "D", "F", "H", "E", "C"]
swap items[3] = D with items[0] = A
["D", "B", "G", "A", "F", "H", "E", "C"]
swap items[2] = G with items[0] = D
["G", "B", "D", "A", "F", "H", "E", "C"]
swap items[1] = B with items[0] = G
["B", "G", "D", "A", "F", "H", "E", "C"]
This is an animation that shows the swaps. See how the green highlight moves from right to left, and the orange highlight randomly selects numbers?
There’s a few things to understand about this implementation:
 The crucial aspect of the implementation is the swapping. Because you swap, you don’t need extra space for the shuffled array.
 The
last
counter runs from the end of the array to0
. You’ve seen this before, withk
from the penandpaper FisherYates approach. This counter ensures that you’ll always pick a random item between0
and the last unshuffled array item.
As a result, the last swap always attempts to swap item 0
with item 0
. Which is pointless! Does that mean you never swap the first item? No! There’s always a chance the first array item gets swapped with any of the others. Every item has the same chance of getting swapped. If it isn’t swapped, the beforelast item 1
is always swapped with the last item 0
because it’s the only item it can swap with!
In case you’re still using Swift 3, the above “swap” in Swift 3 is: swap(&items[last], &items[rand])
Get complementary access to my course, Zero to App Store, and learn how you can build a realtime chat app with Firebase and Swift!
Further Reading
Is that all there is to shuffling an array of strings in Swift? You bet! Most programming algorithms for shuffling you come across will use modern FisherYates, like you’ve seen in this article.
Still looking for a quick code sample you can drop into your Swift project? You can find a Swift extension for shuffling collection types here. Guess what algorithm it uses?
Here’s what you learned in this article:
 How to assess the time and space complexity of an algorithm, and how to express it with Big O Notation
 How to approach creating an algorithm to solve a programming problem, and the steps to move from bruteforce solution to efficient solution
 How to shuffle an array of strings in Swift in O(n) time without using extra memory space
Awesome!
Want to learn more? Check out these resources:
 How To: Map, Reduce and Filter in Swift
 Don’t CopyandPaste Your Code
 How To: Random Numbers in Swift 3
Looking for more info on shuffling, algorithms and Big O? I recommend these resources:
 Shuffling on “Coding Horror” by Jeff Atwood
 Big O Notation on Interview Cake
 FisherYates Shuffle by Mike Bostock
Enjoyed this article? Please share it!
How To: Shuffling An Array In Swift Explained Click To Tweet
Most Popular Content
 How To Develop iOS Apps On A Windows PC
 How To: Build A RealTime Chat App With Firebase And Swift
 How To: Random Numbers in Swift
 Creating A Simple iOS Game With Swift In Xcode (Part 1)
 How To: Pass Data Between View Controllers In Swift (Extended)
 Grand Central Dispatch: MultiThreading With Swift
 Understanding The “Use of Unresolved Identifier” Error In Xcode
Browse Topics
Get complementary access to my course, Zero to App Store, and learn how you can build a realtime chat app with Firebase and Swift!
Yes, Send Me The Free Course!Comments & Thoughts

Reinder de Vries

Mike Critchley