How To: Shuffling An Array In Swift Explained

Written by: Reinder de Vries, August 9 2017, in App Development

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 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 article, you know how to tackle it…

Ready? Let’s go.

  1. The Fisher-Yates Shuffle Algorithm
  2. Algorithm Complexity With Big O Notation
  3. Shuffling An Array Of Strings In O(n) Time
  4. Further Reading

Quick Note: If you came here just for the code snippet, scroll down…

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

  1. Put all the array items in a container
  2. Pull one random item out of the container
  3. Place the item on a table
  4. Pull another random item out
  5. Place it next to the previous item
  6. 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 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 index 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.

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

  1. Write down a set of numbers between 1 and N. This is the sequence of numbers you want to shuffle.
  2. Pick a random number k between 1 and the number of “unstruck” numbers remaining.
  3. 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.
  4. 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.

Grab My Free iOS Development Course

Get complementary access to my course, Zero to App Store, and learn how you can build a real-time chat app with Firebase and Swift!

Yes, Send Me The Free Course!

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.

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

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

In case you’re still using Swift 3, the above “swap” in Swift 3 is: swap(&items[last], &items[rand])

Grab My Free iOS Development Course

Get complementary access to my course, Zero to App Store, and learn how you can build a real-time chat app with Firebase and Swift!

Yes, Send Me The Free Course!

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

Want to learn more? Check out these resources:

Looking for more info on shuffling, algorithms and Big O? I recommend these resources:

Enjoyed this article? Please share it!

How To: Shuffling An Array In Swift Explained Click To Tweet

Written By: Reinder de Vries

Reinder de Vries is an indie app developer who teaches aspiring app developers and marketers how to build their own apps at LearnAppMaking.com. Since 2009 he has developed over 50 apps for iOS, Android and the web, and his code is used by millions of users all over the globe. When Reinder isn't building apps, he enjoys strong espresso and traveling.

Grab My Free iOS Development Course

Get complementary access to my course, Zero to App Store, and learn how you can build a real-time chat app with Firebase and Swift!

Yes, Send Me The Free Course!

Comments & Thoughts


  • Yup! Assuming this is Swift 4 and Xcode 9? Thanks for bringing this to my attention!

    Try this:
    items.swapAt(last, rand)

    Here’s something cool that works too…
    (items[last], items[rand]) = (items[rand], items[last])

    More info: https://github.com/apple/swift-evolution/blob/master/proposals/0173-swap-indices.md

  • Mike Critchley

    Swap is throwing an error when I ran it in a playground. “Overlapping accesses to ‘items’, but modification requires exclusive access; consider calling MutableCollection.swapAt(::)”

    Ah, it’s the swift4 exclusive memory access rule at work here. If you update the swap method you have there with
    items.swapAt(last, rand)
    It works.