Algorithms and data structures in Swift, with explanations!

Overview

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

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

Comments
  • Swift 3 Migration

    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

    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:

    1. Choose a topic below that hasn't been checked off
    2. Check the pull requests to see if anyone is working on your chosen topic
    3. 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

    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

    GitHub Pages

    Checklist

    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.

    Refactors Binary Search implementation to be more Swifty.

    Checklist

    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

    3sum 4sum

    Checklist

    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

    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

    Improvement of Ordered Set and Sorted Set

    Checklist

    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

    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

    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

    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.

    Update words to match the code.

    Checklist

    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

    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

    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.

    image

    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

    Binary search. if -> guard

    Checklist

    Description

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

    opened by prokhorovxo 0
Owner
raywenderlich
raywenderlich
Simplex-Swift - A basic implementation of the Simplex algorithm, written in Swift

Simplex-Swift - A basic implementation of the Simplex algorithm, written in Swift

Evgeny Seliverstov 5 Dec 20, 2022
Fast sorted collections for Swift using in-memory B-trees

Fast Sorted Collections for Swift Using In-Memory B-Trees Overview Reference Documentation Optimizing Collections: The Book What Are B-Trees? Why In-M

null 1.3k Dec 20, 2022
Swift implementation of the longest common subsequence (LCS) algorithm.

SwiftLCS SwitLCS provides an extension of Collection that finds the indexes of the longest common subsequence with another collection. The longest com

Tommaso Madonia 212 Dec 29, 2022
swift-algorithm 눈물이 차올라서 고갤 들어..

swift-algorithm 눈물이 차올라서 고갤 들어.. 알고리즘 정리 Union Find Dynamic Programming 자주 사용되는 문법 1. for문 거꾸로 돌리기 0...n의 반대 for i in stride(from: n, to: 0, by: -1) {

윤예지 6 Nov 8, 2022
AssignmentChalkboard - A simple assignment made in Swift

AssignmentChalkboard This is a simple assignment that i made in Swift

Angelos Staboulis 0 Jan 29, 2022
Algorithms and data structures in Swift, with explanations!

Welcome to the Swift Algorithm Club! Here you'll find implementations of popular algorithms and data structures in everyone's favorite new language Sw

raywenderlich 27.3k Jan 8, 2023
Detailed explanations and implementations of various maths concepts for writing high performance code/algorithms backed with Unit tests.

Detailed explanations and implementations of various maths concepts which can help software Engineers write high performance code/algorithms backed with Unit tests.

Mussa Charles 2 Sep 25, 2022
Artificial intelligence/machine learning data structures and Swift algorithms for future iOS development. bayes theorem, neural networks, and more AI.

Swift Brain The first neural network / machine learning library written in Swift. This is a project for AI algorithms in Swift for iOS and OS X develo

Vishal 331 Oct 14, 2022
Examples of commonly used data structures and algorithms in Swift.

Swift Structures This project provides a framework for commonly used data structures and algorithms written in a new iOS development language called S

Wayne Bishop 2.1k Dec 28, 2022
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

Evgeny Karkan 2.4k Jan 4, 2023
Explanations and samples about the Swift programming language

About Swift Contents Explanations and samples about: Swift Programming Language Swift Standard Library Target audience Developers familiar with object

Nicola Lancellotti - About 74 Dec 29, 2022
List tree data souce to display hierachical data structures in lists-like way. It's UI agnostic, just like view-model and doesn't depend on UI framework

SwiftListTreeDataSource List tree data souce to display hierachical data structures in lists-like way. It's UI agnostic, just like view-model, so can

Dzmitry Antonenka 26 Nov 26, 2022
A collection of tools for debugging, diffing, and testing your application's data structures.

Custom Dump A collection of tools for debugging, diffing, and testing your application's data structures. Motivation customDump diff XCTAssertNoDiffer

Point-Free 631 Jan 3, 2023
Commonly used data structures for Swift

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

Apple 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

Hector Delgado 0 Oct 21, 2021
CloneCorp - Data corpus for the evaluation of cross-language clone detection algorithms

CloneCorp - Data corpus for the evaluation of cross-language clone detection algorithms

FLAGlab 1 Jan 31, 2022
A library of data structures for working with collections of identifiable elements in an ergonomic, performant way.

Swift Identified Collections A library of data structures for working with collections of identifiable elements in an ergonomic, performant way. Motiv

Point-Free 263 Jan 1, 2023
A visual developer tool for inspecting your iOS application data structures.

Tree Dump Debugger A visual developer tool for inspecting your iOS application data structures. Features Inspect any data structure with only one line

null 8 Nov 2, 2022
Classes-and-structures-in-swift - This source files show what is the difference between class and structure

This source files show what is the difference between class and structure You ca

null 0 Jan 4, 2022
CryptoSwift is a growing collection of standard and secure cryptographic algorithms implemented in Swift

CryptoSwift Crypto related functions and helpers for Swift implemented in Swift. (#PureSwift) Note: The master branch follows the latest currently rel

Marcin Krzyzanowski 9.4k Jan 5, 2023