Algorithms and data structures in Swift, with explanations!

raywenderlich

Last update: Jan 8, 2023

Related tags

Overview

Welcome to the Swift Algorithm Club!

Here you'll find implementations of popular algorithms and data structures in everyone's favorite new language Swift, with detailed explanations of how they work.

If you're a computer science student who needs to learn this stuff for exams -- or if you're a self-taught programmer who wants to brush up on the theory behind your craft -- you've come to the right place!

The goal of this project is to explain how algorithms work. The focus is on clarity and readability of the code, not on making a reusable library that you can drop into your own projects. That said, most of the code should be ready for production use but you may need to tweak it to fit into your own codebase.

Code is compatible with Xcode 10 and Swift 4.2. We'll keep this updated with the latest version of Swift. If you're interested in a GitHub pages version of the repo, check out this.

😍 Suggestions and contributions are welcome! 😍

Important links

What are algorithms and data structures? Pancakes!

Why learn algorithms? Worried this isn't your cup of tea? Then read this.

Big-O notation. We often say things like, "This algorithm is O(n)." If you don't know what that means, read this first.

Algorithm design techniques. How do you create your own algorithms?

How to contribute. Report an issue to leave feedback, or submit a pull request.

Where to start?

If you're new to algorithms and data structures, here are a few good ones to start out with:

The algorithms

Searching

Linear Search. Find an element in an array.
Binary Search. Quickly find elements in a sorted array.
Count Occurrences. Count how often a value appears in an array.
Select Minimum / Maximum. Find the minimum/maximum value in an array.
k-th Largest Element. Find the k-th largest element in an array, such as the median.
Selection Sampling. Randomly choose a bunch of items from a collection.
Union-Find. Keeps track of disjoint sets and lets you quickly merge them.

String Search

Brute-Force String Search. A naive method.
Boyer-Moore. A fast method to search for substrings. It skips ahead based on a look-up table, to avoid looking at every character in the text.
Knuth-Morris-Pratt. A linear-time string algorithm that returns indexes of all occurrencies of a given pattern.
Rabin-Karp Faster search by using hashing.
Longest Common Subsequence. Find the longest sequence of characters that appear in the same order in both strings.
Z-Algorithm. Finds all instances of a pattern in a String, and returns the indexes of where the pattern starts within the String.

Sorting

It's fun to see how sorting algorithms work, but in practice you'll almost never have to provide your own sorting routines. Swift's own sort() is more than up to the job. But if you're curious, read on...

Basic sorts:

Fast sorts:

Hybrid sorts:

Introsort

Special-purpose sorts:

Bad sorting algorithms (don't use these!):

Compression

Run-Length Encoding (RLE). Store repeated values as a single byte and a count.
Huffman Coding. Store more common elements using a smaller number of bits.

Miscellaneous

Shuffle. Randomly rearranges the contents of an array.
Comb Sort. An improve upon the Bubble Sort algorithm.
Convex Hull.
Miller-Rabin Primality Test. Is the number a prime number?
MinimumCoinChange. A showcase for dynamic programming.
Genetic. A simple example on how to slowly mutate a value to its ideal form, in the context of biological evolution.
Myers Difference Algorithm. Finding the longest common subsequence of two sequences.

Mathematics

Greatest Common Divisor (GCD). Special bonus: the least common multiple.
Permutations and Combinations. Get your combinatorics on!
Shunting Yard Algorithm. Convert infix expressions to postfix.
Karatsuba Multiplication. Another take on elementary multiplication.
Haversine Distance. Calculating the distance between 2 points from a sphere.
Strassen's Multiplication Matrix. Efficient way to handle matrix multiplication.
CounterClockWise. Determining the area of a simple polygon.

Machine learning

k-Means Clustering. Unsupervised classifier that partitions data into k clusters.
k-Nearest Neighbors
Linear Regression. A technique for creating a model of the relationship between two (or more) variable quantities.
Logistic Regression
Neural Networks
PageRank
Naive Bayes Classifier
Simulated annealing. Probabilistic technique for approximating the global maxima in a (often discrete) large search space.

Data structures

The choice of data structure for a particular task depends on a few things.

First, there is the shape of your data and the kinds of operations that you'll need to perform on it. If you want to look up objects by a key you need some kind of dictionary; if your data is hierarchical in nature you want a tree structure of some sort; if your data is sequential you want a stack or queue.

Second, it matters what particular operations you'll be performing most, as certain data structures are optimized for certain actions. For example, if you often need to find the most important object in a collection, then a heap or priority queue is more optimal than a plain array.

Most of the time using just the built-in Array, Dictionary, and Set types is sufficient, but sometimes you may want something more fancy...

Variations on arrays

Array2D. A two-dimensional array with fixed dimensions. Useful for board games.
Bit Set. A fixed-size sequence of n bits.
Fixed Size Array. When you know beforehand how large your data will be, it might be more efficient to use an old-fashioned array with a fixed size.
Ordered Array. An array that is always sorted.
Rootish Array Stack. A space and time efficient variation on Swift arrays.

Queues

Stack. Last-in, first-out!
Queue. First-in, first-out!
Deque. A double-ended queue.
Priority Queue. A queue where the most important element is always at the front.
Ring Buffer. Also known as a circular buffer. An array of a certain size that conceptually wraps around back to the beginning.

Lists

Linked List. A sequence of data items connected through links. Covers both singly and doubly linked lists.
Skip-List. Skip List is a probabilistic data-structure with same logarithmic time bound and efficiency as AVL/ or Red-Black tree and provides a clever compromise to efficiently support search and update operations.

Trees

Tree. A general-purpose tree structure.
Binary Tree. A tree where each node has at most two children.
Binary Search Tree (BST). A binary tree that orders its nodes in a way that allows for fast queries.
Red-Black Tree. A self balancing binary search tree.
Splay Tree. A self balancing binary search tree that enables fast retrieval of recently updated elements.
Threaded Binary Tree. A binary tree that maintains a few extra variables for cheap and fast in-order traversals.
Segment Tree. Can quickly compute a function over a portion of an array.
- Lazy Propagation
kd-Tree
Sparse Table. Another take on quickly computing a function over a portion of an array, but this time we'll make it even quicker!.
Heap. A binary tree stored in an array, so it doesn't use pointers. Makes a great priority queue.
Fibonacci Heap
Trie. A special type of tree used to store associative data structures.
B-Tree. A self-balancing search tree, in which nodes can have more than two children.
QuadTree. A tree with 4 children.
Octree. A tree with 8 children.

Hashing

Hash Table. Allows you to store and retrieve objects by a key. This is how the dictionary type is usually implemented.
Hash Functions

Sets

Bloom Filter. A constant-memory data structure that probabilistically tests whether an element is in a set.
Hash Set. A set implemented using a hash table.
Multiset. A set where the number of times an element is added matters. (Also known as a bag.)
Ordered Set. A set where the order of items matters.

Graphs

Graph
Breadth-First Search (BFS)
Depth-First Search (DFS)
Shortest Path on an unweighted tree
Single-Source Shortest Paths
Minimum Spanning Tree on an unweighted tree
Minimum Spanning Tree
All-Pairs Shortest Paths
Dijkstra's shortest path algorithm
A-Star

Puzzles

A lot of software developer interview questions consist of algorithmic puzzles. Here is a small selection of fun ones. For more puzzles (with answers), see here and here.

Learn more!

Like what you see? Check out Data Structures & Algorithms in Swift, the official book by the Swift Algorithm Club team!

You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way. Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees, and tries.

Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort, and quicksort. Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations!

You can find the book on the raywenderlich.com store.

Credits

The Swift Algorithm Club was originally created by Matthijs Hollemans.

It is now maintained by Vincent Ngo, Kelvin Lau, and Richard Ash.

The Swift Algorithm Club is a collaborative effort from the most algorithmic members of the raywenderlich.com community. We're always looking for help - why not join the club? :]

License

All content is licensed under the terms of the MIT open source license.

By posting here, or by submitting any pull request through this forum, you agree that all content you submit or create, both code and text, is subject to this license. Razeware, LLC, and others will have all the rights described in the license regarding this content. The precise terms of this license may be found here.

Comments

Swift 3 Migration
And... we're done!

Thanks everyone for pitching in!

Xcode 8 and Swift 3 will be formally released soon and we need to migrate everything to Swift 3.

Want to help out with the migration? Awesome! :]

Please follow this process for migrating to Swift 3

Download the Xcode 8.X

Create a pull request to "claim" an algorithm or data structure you'd like to migrate. Just so multiple people don't work on the same thing.

Migrate the algorithm/data structure project, playground, tests and readme to Swift 3

Uncomment test project in .travis.yml so it will run on our Xcode 8 Travis CI build server

Comment in the pull request when the changes are ready to be merged

Suggestions and feedback is welcome!

List of algorithms to be migrated to Swift 3

nil

Completed Migrations

[x] AVL Tree #183

[x] All-Pairs Shortest Paths #347

[x] Array2D #189

[x] B-Tree #203

[x] Binary Search Tree

[x] Binary Search #184

[x] Binary Tree #213

[x] Bit Set #194

[x] Bloom Filter #195

[x] Bounded Priority Queue #218

[x] Boyer-Moore #248

[x] Breadth-First #237

[x] Brute-Force String Search #239

[x] Bubble Sort (no code)

[x] Bucket Sort #281

[x] Comb Sort #350

[x] Combinatorics #270

[x] Count Occurrences #201

[x] Counting Sort #235

[x] Depth-First Search #238

[x] Deque #303

[x] Fixed Size Array #271

[x] Fizz Buzz #229

[x] GCD #219

[x] Graph #267

[x] Hash Set #276

[x] Hash Table #216

[x] Heap Sort #334

[x] Heap 3945383d306ac027f779461789d6b0deddca4348

[x] Huffman Coding #344

[x] Insertion Sort #198

[x] K-Means #349

[x] Kth Largest Element #228

[x] Linear Regression #283

[x] Linear Search #200

[x] Linked List #250

[x] Longest Common Subsequence #243

[x] Merge Sort #199

[x] Minimum Edit Distance #302

[x] Minimum Spanning Tree (Unweighted) #345

[x] Monty Hall Problem #241

[x] Ordered Array #232

[x] Ordered Set #234

[x] Palindromes #187

[x] Priority Queue #233

[x] Queue #197

[x] Quicksort #217

[x] Radix Sort #347

[x] Radix Tree #242

[x] Red-Black Tree #214

[x] Ring Buffer #265

[x] Run-Length Encoding #364

[x] Segment Tree #220

[x] Selection Sampling (no changes necessary)

[x] Select Minimum Maximum #333

[x] Selection Sort

[x] Set Cover (Unweighted) #366

[x] Shell Sort #260

[x] Shortest Path (Unweighted) #343

[x] Shuffle #273 #274

[x] Shunting Yard #365

[x] Single-Source Shortest Paths (Weighted) #356

[x] Stack #196

[x] Ternary Search Tree

[x] Topological Sort #259

[x] Treap #251

[x] Threaded Binary Tree #367

[x] Tree #193

[x] Trie #208

[x] Two-Sum Problem #266

[x] Union-Find #192
opened by chris-pilcher 35
Swift 4 Migration
Update

Thanks everyone for helping out with the migration! Another year, another migration complete :]

It's that time of the year again. Swift 4 is imminent, so it's time to begin migration. Swift 3 to Swift 4 has been relatively painless compared to other years, so things should go rather smoothly!

Migration Procedure:

Choose a topic below that hasn't been checked off

Check the pull requests to see if anyone is working on your chosen topic

Make a pull request to let others know that you're currently working on your chosen topic

Add the following code snippet at the top of each playground file:

// last checked with Xcode 9.0b4 #if swift(>=4.0) print("Hello, Swift 4!") #endif

Make sure the code for the topic compiles correctly with the latest Xcode 9 beta (currently beta 4).

Make sure that the README.md file reflects the updated playground

Current Progress

[x] AVL Tree

[x] All-Pairs Shortest Paths

[x] Array2D

[x] B-Tree

[x] Binary Search Tree

[x] Binary Search

[x] Binary Tree

[x] Bit Set

[x] Bloom Filter

[x] Bounded Priority Queue

[x] Boyer-Moore

[x] Breadth-First Search

[x] Brute-Force String Search

[x] Bubble Sort

[x] Bucket Sort

[x] Comb Sort

[x] Combinatorics

[x] Convex Hull

[x] Count Occurrences

[x] Counting Sort

[x] Depth-First Search

[x] Deque

[x] Dijkstra Algorithm

[x] DiningPhilosophers

[x] Fixed Size Array

[x] Fizz Buzz

[x] GCD

[x] Graph

[x] Hash Set

[x] Hash Table

[x] HaversineDistance

[x] Heap Sort

[x] Heap

[x] Huffman Coding

[x] Insertion Sort

[x] K-Means

[x] Karatsuba Multiplication

[x] Knuth-Morris-Pratt

[x] Kth Largest Element

[x] LRU Cache

[x] Linear Regression

[x] Linear Search

[x] Linked List

[x] Longest Common Subsequence

[x] Merge Sort

[x] Miller-Rabin Primality Test

[x] Minimum Edit Distance

[x] Minimum Spanning Tree (Unweighted)

[x] Minimum Spanning Tree

[x] MinimumCoinChange

[x] Monty Hall Problem

[x] Ordered Array

[x] Ordered Set

[x] Palindromes

[x] Priority Queue

[x] QuadTree

[x] Queue

[x] Quicksort

[x] Rabin-Karp

[x] Radix Sort

[x] Radix Tree

[x] Red-Black Tree

[x] Ring Buffer

[x] Rootish Array Stack

[x] Run-Length Encoding

[x] Segment Tree

[x] Select Minimum Maximum

[x] Selection Sampling

[x] Selection Sort

[x] Set Cover (Unweighted)

[x] Shell Sort

[x] Shortest Path (Unweighted)

[x] Shuffle

[x] Shunting Yard

[x] Single-source Shortest Paths(Weighted)

[x] Skip-List

[x] Slow Sort

[x] Stack

[x] Strassen Matrix Multiplication

[x] Ternary Search Tree

[x] Threaded Binary Tree

[x] Topological Sort

[x] Treap

[x] Tree

[x] Trie

[x] Two-Sum Problem

[x] Union-Find

[x] Z-Algorithm
opened by kelvinlauKL 27
Claim several data structures and algorithms for a group project

I am part of a group of four people. Our final project for one of our classes is to contribute to an open source project. We would like to work on this repository! We will be working on several data structures and algorithms, and we'd like to claim some now. Note that we will probably "claim" a few others later, depending on availability.

Currently "claimed" projects: Trie Radix Sort Radix Tree Red Black Tree Threaded Binary Tree

opened by jftung 18
GitHub Pages
Checklist

[x] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

This pull request is based on #640.

The script requires 2 environment variables to run on Travis CI:

USERNAME - username of the repository's owner, raywenderlich in your case.

TOKEN - personal access token with public_repo permission.

The token is used only within the script for the 2 following purposes:

Increase the limit of network calls to GitHub API Markdown to 5000 per hour (unauthenticated request caps at 60).

Push to gh-pages remote branch.
opened by aquarchitect 17
Refactors Binary Search implementation to be more Swifty.
Checklist

[x] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

This involved converting the global function into methods of Collection. By doing so, the recursive version no longer needs to take a search range as a parameter. It also made both the recursive and iterative versions of the algorithm usable on other collection types besides Array. Tests were also refactored to test both versions of the algorithm.
opened by philium 13
3sum 4sum
Checklist

[x] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

Follow up 2Sum problem. How to solve 3Sum and 4Sum problem? What’s their relationships? Could we get some generic idea to solve this kind of problems? I give the explanation here.
opened by remlostime 12
Add unit testing

I think that we need unit testing to validate some complicated algorithms, even the simplest ones need testing to avoid regressions.

XCTests is not supported in playgrounds, hope that it will be in the future. I think that we should organize the project to have a test target.

opened by samirGuerdah 12
Improvement of Ordered Set and Sorted Set
Checklist

[X] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

Add doc for apple ordered set

Split ordered set (rename to sorted set) and apple ordered set (rename to ordered set)
opened by remlostime 10
Show path to Node

Hello There, this algorithm is just what Im looking for, but I have an issue, and would be great if someone can help me. For Example, from node a to h the distance is 3. Is there A Way to know which is the path of that distance? Maybe just printing A B E H would help for what I need!

opened by magonicolas 10
Update README.markdown

My native programming language is Java and I am new to swift. To the best of my knowledge I have translated from Java to Swift. Thanks for the opportunity and don't be afraid to hurt my feelings. I'm open to any feedback. This was merely the first step of many.

opened by jherna37 10
Unit tests for Array2D and AVLTree data structures

Hi @hollance . I'm Barbara and I'd like to do a contribution to the project. I've added 2 XCode project with its respective tests targets for Array2D and AVLTree. I've include some functional and performance tests. Not all the possible tests are covered, but I enabled code coverage data so more tests could be added in the future. There is also a small bug fix after some of the tests failed, for the class AVLTree: the parent property was not set on children when creating a parent node.

I hope these changes help and I will continue adding more tests, in upcoming contributions, for these structures and the rest of the project. I really like this initiative, I find it useful in many sense, to learn, to practice, to improve and generate re-usable algorithms and data structures. Thanks for creating the project.

While working on that, I was told about a website called, Rosetta. Have you heard before about this?. I think it might be interesting to take some algorithms from there, solve them in this repo and upload the solutions to Rosetta, they have around 781 problems solved and support 605 programming languages, including Swift.

opened by barbaramartina 10
Update words to match the code.
Checklist

[x] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

Seems like some names of variables used in the sentence is out of date. Here is an update to align the variables' names with what they look like in the code block.
opened by davidleee 1
There are some mistakes with the README.markdown and Selection Sampling code improvement

Brief Intro

https://github.com/raywenderlich/swift-algorithm-club/pull/997 I have created this PR for that issue, there are some mistakes in the README files and also a little improvement for the Selection Sampling example function.

More Details

swap(&a[i], &a[r]) can be written like a.swapAt(i, r) That would be remove the error called "Overlapping accesses to 'a', but modification requires exclusive access; consider calling MutableCollection.swapAt(::)"

opened by efemazlumoglu 0
LinkedList`s removeAll method and default deinit may cause stack overflow

When triggering removeAll or deinit of very long LinkedList ( like 1...10000000 integers storage)，you will get stack overflow. The reason is nodes` recursive releasing.

From the image above you will see recursive node deinit pushing into the stack accumulatively and this will cause crash with size increasing.

I suggest to fix this issue by rewriting removeAll, not simply 'self.head = nil', but using a while-loop to releasing each node, and calling removeAll in LinkedList deinit.

opened by NickMeepo 0
Binary search. if -> guard
Checklist

[x] I've looked at the contribution guidelines.

[x] This pull request is complete and ready for review.

Description

Replace if with guard https://github.com/raywenderlich/swift-style-guide#golden-path
opened by prokhorovxo 0

Owner

raywenderlich

GitHub

EKAlgorithms contains some well known CS algorithms & data structures.

EKAlgorithms EKAlgorithms is a set of computer exercises implemented in Objective-C. Data structures, well known algorithms, CS curiosities, you name

2.4k Jan 4, 2023

Commonly used data structures for Swift

Swift Collections is an open-source package of data structure implementations for the Swift programming language.

2.7k Jan 5, 2023

Simple implementations of various dynamic data structures in Swift.

SwiftDataStructures Example To run the example project, clone the repo, and run pod install from the Example directory first. Requirements Installatio

0 Oct 21, 2021

Mendel - Swift miliframework for implementing evolutionary/genetic algorithms

Mendel Mendel - Swift miliframework for implementing evolutionary/genetic algorithms. Or, you know, Gregor Mendel. This started out as an exercise in

139 Oct 26, 2022

Swivl - A set of BLAS-accelerated linerar algebra structures and functions

Swivl - Swift Vector Library A set of BLAS-accelerated linerar algebra structure

0 Jan 19, 2022

KeyPathKit is a library that provides the standard functions to manipulate data along with a call-syntax that relies on typed keypaths to make the call sites as short and clean as possible.

KeyPathKit Context Swift 4 has introduced a new type called KeyPath, with allows to access the properties of an object with a very nice syntax. For in