Shuffling Arrays in Swift with Fisher-Yates

By Joel Perez | Last Updated on September 5th, 2023 1:17 pm | 4-min read

Algorithms are fun! In this tutorial, 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 must-know 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 tutorial, you know how to tackle it…

The Fisher-Yates 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, you’re looking for array.shuffle() and array.shuffled(). We’re about to have a lot more fun than that though, so stick around!

The Fisher-Yates 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 understand it better. There’s nothing worse than building an app from random pieces you found on the internet that you don’t understand!

The Naive Approach

How would you shuffle an array of strings yourself?

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 _ in 0..

First, create two arrays items and shuffled. The items array contains an ordered sequence of the characters A to H. The shuffled array is empty.

Then, loop from 0 to 7, i.e. loop 8 times, once for all the times in the items array. For every iteration, do this:

Pick a random number between 0 and items.count (non-inclusive).
Get item for that index from items and append it to the shuffled array.
Remove the item from items to avoid picking the same number twice.

Finally, print out the shuffled array.

It works, but this isn’t the most efficient approach to shuffle an array! This is why it’s called the naive approach. It’s working OK, but with a bit more effort we can get the algorithm to run more efficiently.

The Fisher-Yates Algorithm

A better algorithm to shuffle an array is the Fisher-Yates shuffle algorithm. This algorithm has a pen-and-paper approach and a modern approach. The modern approach is more efficient, but let’s first look at the pen-and-paper 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. Like this:

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 k-th 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.

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 tutorial.

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 front-end, 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 real-world 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.

Time Complexity

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. What time complexities could that algorithm have?

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 when you put twice as much items in, it takes twice as much time to complete.

When the complexity is O(n2), 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(n2).

Quick Note: More efficient, not necessarily faster. An algorithm with O(n) complexity can take more “absolute” time to complete than another algorithm with O(n2) 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.

What’s the time complexity of the Fisher-Yates algorithm? It’s O(n2).

Intuitively, you’d say that its complexity is linear: O(n). After all, you do more work to shuffle more items. It seems like you touch every item in the array once. So why quadratic time complexity?

It’s because of step 3 in the algorithm: you have to count out the k-th 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 this as two nested for-loops. 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 k-th item.

See how you’re iterating the every item, for every item? That’s items × items; items2; and O(n2). The larger the input, the more items you have to randomly select, and the more items you have to count out.

Space Complexity

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 Fisher-Yates 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 trade-off 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.

Shuffling An Array Of Strings In O(n) Time

What can you do to improve the efficiency of the Fisher-Yates 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(n2) 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 in-place. This ensures that you wont use any extra space.

To achieve an in-place 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.random(in: 0..

First, define an array items and take the index for the last item (items.count – 1) and then assign it to last.

Then, while last is greater than 0:

Take a random index from the array between 0 and last (non-inclusive)

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

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 to 0. You’ve seen this before, with k from the pen-and-paper Fisher-Yates approach. This counter ensures that you’ll always pick a random item between 0 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 before-last item 1 is always swapped with the last item 0 because it’s the only item it can swap with!