# Shuffling Arrays in Swift with Fisher-Yates

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…

Ready? Let’s go.

- 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 shuffled = [String]()

for _ in 0..<items.count {

let rand = Int.random(in: 0..<items.count)

shuffled.append(items[rand])

items.remove(at: rand)

}

print(shuffled)

In the above code, this happens:

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

- Pick a random number between
- 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.

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 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(n*, the time it takes to complete is^{2})*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 “absolute” 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*.

What’s the *time complexity* of the Fisher-Yates 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. 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*; *items ^{2}*; and

*O(n*. The larger the input, the more items you have to randomly select, and the more items you have to count out.

^{2})### 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(n*to^{2})*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 last = items.count - 1

while(last > 0)

{

let rand = Int.random(in: 0..<last)

print("swap items[\(last)] = \(items[last]) with items[\(rand)] = \(items[rand])")

items.swapAt(last, rand)

last -= 1

print(items)

}

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 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`

- 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 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!

## 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 Fisher-Yates, like you’ve seen in this tutorial.

Here’s what you learned in this tutorial:

- 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 brute-force solution to efficient solution
- How to shuffle an array of strings in Swift in
*O(n)*time without using extra memory space

Awesome! 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
- Fisher-Yates Shuffle by Mike Bostock

Want to learn more? Check out these resources: