Algorithms and data structures in Swift, with explanations!
Clone or download
Latest commit 319f94d Dec 3, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.github Deleted the checkboxes in favour of using labels Oct 7, 2017
3Sum and 4Sum Add syntax color for code Oct 21, 2017
AVL Tree Updated AVL Tree to Swift 4.2 Oct 14, 2018
All-Pairs Shortest Paths Swift 4.2 Migration #748 - Depth First Search migrated to Swift 4.2 Nov 6, 2018
Array2D Swift 4.2 [Array2D] Oct 4, 2018
B-Tree Compile for Swift 4.2 Nov 7, 2018
Binary Search Tree [Swift 4.2] Update Binary Search Tree Oct 5, 2018
Binary Search [Swift 4.2] Update Binary Search Tree Oct 5, 2018
Binary Tree Updated Binary Tree to Swift 4.2 Oct 26, 2018
Bit Set Update BitSet to Swift 4.2 Oct 26, 2018
Bloom Filter Update README according to comments. Nov 1, 2018
Bounded Priority Queue Update Bounded Priority Queue to Swift 4.2 Oct 26, 2018
Boyer-Moore-Horspool Merge pull request #817 from sticksen/boyer-moore-swift42 Dec 4, 2018
Breadth-First Search Update Breadth First Search to Swift 4.2 Oct 26, 2018
Brute-Force String Search Update README.markdown Mar 14, 2018
Bubble Sort Merge remote-tracking branch 'upstream/master' Nov 13, 2018
Bucket Sort Add credit to README. Oct 5, 2018
Comb Sort Removes Swift 4.0 checks and updates the Swift version to 4.2. Oct 24, 2018
Combinatorics Update Combinatorics to match Swift 4 API Apr 11, 2018
Convex Hull [Swift 4.2] Update Convex Hull Oct 8, 2018
Count Occurrences Count Occurrences to Swift 4 Jul 26, 2017
Counting Sort [Swift 4] Update Counting Sort Jul 31, 2017
Depth-First Search Swift 4.2 support Depth-First Search Nov 6, 2018
Deque Update Deque up to Swift 4.2. Oct 4, 2018
Dijkstra Algorithm [Swift 4.2] Dijkstra Algorithm Oct 5, 2018
DiningPhilosophers Add credit to README.md. Oct 11, 2018
Egg Drop Problem Merge pull request #770 from alaphao/swift4.2-egg-drop-problem Nov 4, 2018
Encode and Decode Tree Address comments and update the code to sync up with readme Jan 15, 2018
Fixed Size Array Remove notice from FixedSizeArray playground. Oct 4, 2018
Fizz Buzz [Swift 4.2] Update Fizz Buzz Oct 8, 2018
GCD Remove notice from GCD playground. Oct 4, 2018
Graph [Swift 4.2] Graph Oct 4, 2018
Hash Set [Swift 4.2] Updated Hash Set Nov 12, 2018
Hash Table [Swift 4.2] Updated Hash Table Nov 12, 2018
Hashed Heap Fixes indentation to 2 spaces. Aug 9, 2017
HaversineDistance Update Contents.swift Nov 12, 2018
Heap Sort [Swift 4.2] Updated Heap Sort Nov 12, 2018
Heap [Swift 4.2] Updated Heap Nov 12, 2018
Huffman Coding update Huffman Coding to Swift 4.2 Oct 13, 2018
Images Added link to Swift Alg Club book Apr 17, 2018
Insertion Sort Update Insertion Sort up to Swift 4.2. Oct 4, 2018
Introsort English Edit Feb 7, 2018
K-Means [Swift 4.2] Update K-Means Oct 6, 2018
Karatsuba Multiplication fix indentation typos in the README.md Oct 15, 2018
Knuth-Morris-Pratt Updated Knuth-Morris-Pratt to Swift 4.2 Oct 14, 2018
Kth Largest Element Updated Kth largest element to Swift 4.2 Oct 14, 2018
LRU Cache Updated LRU Cache to Swift 4.2 Oct 13, 2018
Linear Regression Confirmed Linear Regression to work with Swift 4.2 Oct 31, 2018
Linear Search [Swift 4.2] Updated Linear Search Oct 23, 2018
Linked List Merge pull request #777 from varun989/master Nov 4, 2018
Longest Common Subsequence Update README.markdown Apr 23, 2018
Merge Sort [Swift 4.2] Merge Sort Oct 5, 2018
Miller-Rabin Primality Test [Swift 4.2] Update Miller-Rabin Primality Test Oct 15, 2018
Minimum Edit Distance Merge branch 'master' into MinimumEditDistance-Swift4 Aug 18, 2017
Minimum Spanning Tree (Unweighted) Updated MST (Unweighted) tests to Swift 4.2 Oct 12, 2018
Minimum Spanning Tree Updated MST to Swift 4.2 Oct 12, 2018
MinimumCoinChange [Swift 4] Update Minimum Coin Change Aug 26, 2017
Monty Hall Problem Update Monty Hall to Swift 4.2 Oct 13, 2018
Multiset Update Multiset to Swift 4.2 Oct 13, 2018
Naive Bayes Classifier Update Naive Bayes Classifier to Swift 4 Jul 31, 2017
Octree add readme Oct 9, 2017
Ordered Array Migrate to Swift 4.2 Oct 13, 2018
Ordered Set Split sorted set and ordered set Nov 19, 2017
Palindromes updating README Oct 18, 2018
Priority Queue [Swift 4] Update Priority Queue Aug 26, 2017
QuadTree Update Quad Tree to Swift 4.2 Oct 13, 2018
Queue [Swift 4.2] Queue Oct 5, 2018
Quicksort Merge pull request #723 from jack3010/master Jun 9, 2018
Rabin-Karp Fix Jun 14, 2018
Radix Sort Updated Radix Sort Tests to Swift 4.2 Oct 21, 2018
Radix Tree RadixTree syntax updated to Swift 4 Dec 20, 2017
Red-Black Tree Add credit to README.md. Oct 11, 2018
Ring Buffer Update Ring Buffer to Swift 4.2 Oct 13, 2018
Rootish Array Stack [Swift 4] Update Rootish Array Stack Aug 2, 2017
Run-Length Encoding Missing a curly Brace, opps. Sep 21, 2017
Segment Tree Added a few extra words describing lazy propagation. Oct 9, 2017
Select Minimum Maximum [Swift 4] Update Select Minimum Maximum Aug 27, 2017
Selection Sampling Update README.markdown Jan 31, 2018
Selection Sort [Swift 4.2] Updated Selection Sort Oct 23, 2018
Set Cover (Unweighted) Updated random number generation to Swift 4.2 Nov 1, 2018
Shell Sort Merge pull request #606 from carlosaking/Shell-Sort-Swift4 Sep 11, 2017
Shortest Path (Unweighted) [Swift 4] Update Shortest Path (Unweighted) Aug 27, 2017
Shuffle [Swift 4.2] Update Shuffle Oct 3, 2018
Shunting Yard Shunting Yard working fine with Swift 4.2 and Xcode 10 Nov 1, 2018
Simulated annealing Fixes Issue#371: Simulated Annealing demo crashes Aug 3, 2018
Single-Source Shortest Paths (Weighted) [Swift 4] Update Single-Source Shortest Paths (Weighted) Aug 27, 2017
Singly Linked List Fix the position of the opening brace to conform to the style guide Nov 8, 2017
Skip-List [Swift 4] Update Skip List Aug 2, 2017
Slow Sort Removes Swift 4.0 check. Oct 24, 2018
Sorted Set Update Sorted Set to Swift 4.2 Oct 17, 2018
Sparse Table Fix typo "Idempotent" Mar 28, 2018
Splay Tree Fixed broken youtube link in splay tree readme Mar 31, 2018
Stack Added Markdown Documentation to Stack playground Nov 8, 2018
Strassen Matrix Multiplication Remove notice from Strassen Multiplication Matrix playground Oct 5, 2018
Ternary Search Tree [Swift 4] Update Ternary Search Tree Aug 2, 2017
Threaded Binary Tree [Swift 4.2] Threaded Binary Tree Oct 6, 2018
Topological Sort [Swift 4] Update Topological Sort Jul 30, 2017
Treap [Swift 4] Update Treap Aug 1, 2017
Tree Adds links to written tutorials on raywenderlich.com Oct 22, 2017
Trie Standardize Trie indentation to 2 spaces Oct 27, 2018
Two-Sum Problem updated readme for 2 sum problem with swift 4.2 Oct 6, 2018
Union-Find update union-find to swift 4.2 Oct 28, 2018
Z-Algorithm Update Z-Algorithm up to Swift 4.2. Oct 4, 2018
swift-algorithm-club.xcworkspace Merge pull request #817 from sticksen/boyer-moore-swift42 Dec 4, 2018
.gitignore No longer gitignore xcworkspace May 9, 2016
.swiftlint.yml Fix "found unknown escape character" while trying to run swiftlint 0.… Apr 28, 2017
.travis.yml [Swift 4.2] added tests Oct 8, 2018
Algorithm Design.markdown Divide and Conquer Jun 9, 2017
Big-O Notation.markdown Fixed two misspellings in O(n!) example Apr 21, 2018
LICENSE.txt Add name to articles Jan 28, 2016
README.markdown Update README.markdown Sep 26, 2018
Under Construction.markdown URL encode links in Markdown files Mar 25, 2017
What are Algorithms.markdown Pancakes! Feb 10, 2016
Why Algorithms.markdown Tweak main page Feb 6, 2016
gfm-render.sh GitHub Pages Script Updates (#670) Dec 2, 2017
install_swiftlint.sh CHMOD install_swiftlint.sh Jun 8, 2016

README.markdown

Swift Algorithm Club

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 9 and Swift 4. We'll keep this updated with the latest version of Swift.

😍 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

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:

Special-purpose sorts:

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

Compression

Miscellaneous

Mathematics

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

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!

Data Structures & Algorithms in Swift Book

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.

Build Status