Skip to content
Algorithms and data structures in Swift, with explanations!
Swift
Find file
Latest commit 5012add @hollance Merge pull request #86 from hamdullahshah/patch-1
Fixed the count condition
Failed to load latest commit information.
AVL Tree added more test cases to test the validity of the AVL Tree
Array2D Rename variable to matrix
B Tree Add B-tree paragraph placeholder,
Binary Search Tree Improve removing node with two children
Binary Search Merge pull request #65 from chris-pilcher/travis-ci
Binary Tree Tons of tiny text tweaks
Bit Set Tons of tiny text tweaks
Bloom Filter Merge pull request #65 from chris-pilcher/travis-ci
Bounded Priority Queue Clean up of Bounded Priority Queue
Boyer-Moore Tons of tiny text tweaks
Breadth-First Search Improve explanation of DFS
Brute-Force String Search Put brute-force string search in its own folder
Bubble Sort Add bubble sort (but not really)
Combinatorics Tons of tiny text tweaks
Count Occurrences Tons of tiny text tweaks
Depth-First Search Improve explanation of DFS
Deque Tons of tiny text tweaks
Fixed Size Array Tons of tiny text tweaks
Fizz Buzz Tons of tiny text tweaks
GCD Tons of tiny text tweaks
Graph Tweak graph images and text
Hash Set Tons of tiny text tweaks
Hash Table Tons of tiny text tweaks
Heap Sort Merge pull request #65 from chris-pilcher/travis-ci
Heap Merge pull request #65 from chris-pilcher/travis-ci
Huffman Coding Tons of tiny text tweaks
Images Travis: adding contribution guidelines for Travis-CI test projects
Insertion Sort Merge pull request #65 from chris-pilcher/travis-ci
K-Means Tweaks to K-Means code, text, and images
Kth Largest Element Tons of tiny text tweaks
Linear Search Tons of tiny text tweaks
Linked List update readme to include refactored code
Longest Common Subsequence Small tweaks to text and code
Merge Sort Tons of tiny text tweaks
Minimum Spanning Tree (Unweighted) Shortest path and minimum spanning tree are for unweighted graphs only
Monty Hall Problem Tons of tiny text tweaks
Ordered Array Tons of tiny text tweaks
Priority Queue Including all files. Changing all schemes to "shared"
Queue modified percentage
Quicksort Merge pull request #65 from chris-pilcher/travis-ci
Ring Buffer Tons of tiny text tweaks
Run-Length Encoding Merge pull request #65 from chris-pilcher/travis-ci
Segment Tree Tons of tiny text tweaks
Select Minimum Maximum Merge pull request #65 from chris-pilcher/travis-ci
Selection Sampling Tons of tiny text tweaks
Selection Sort Merge pull request #65 from chris-pilcher/travis-ci
Shell Sort Merge pull request #65 from chris-pilcher/travis-ci
Shortest Path (Unweighted) Shortest path and minimum spanning tree are for unweighted graphs only
Shuffle Tons of tiny text tweaks
Shunting Yard Tons of tiny text tweaks
Stack Merge pull request #65 from chris-pilcher/travis-ci
Topological Sort Fix error in depth-first search
Tree Tons of tiny text tweaks
Two-Sum Problem Tons of tiny text tweaks
Union-Find Tons of tiny text tweaks
.gitignore Add gitignore
.travis.yml Adds LCS tests on travis
Algorithm Design.markdown Tons of tiny text tweaks
Big-O Notation.markdown Add link to rosettacode.org
How to Contribute.markdown Add note about construction badge
LICENSE.txt Add name to articles
README.markdown Tweaks to K-Means code, text, and images
What are Algorithms.markdown Pancakes!
Why Algorithms.markdown Tweak main page

README.markdown

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.

All code is compatible with Xcode 7.2 and Swift 2.1. We'll keep this updated with the latest version of Swift.

This is a work in progress. More algorithms will be added soon. :-)

:heart_eyes: Suggestions and contributions are welcome! :heart_eyes:

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.
  • Rabin-Karp
  • Longest Common Subsequence. Find the longest sequence of characters that appear in the same order in both strings.

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:

Special-purpose sorts:

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

Compression

Miscellaneous

  • Shuffle. Randomly rearranges the contents of an array.

Mathematics

Machine learning

  • k-Means Clustering. Unsupervised classifier that partitions data into k clusters.
  • k-Nearest Neighbors
  • Linear Regression
  • Logistic Regression
  • Neural Networks
  • PageRank

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.

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.
  • Bounded Priority Queue. A queue that is bounded to have a limited number of elements. :construction:
  • 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

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.
  • AVL Tree. A binary search tree that balances itself using rotations. :construction:
  • Red-Black Tree
  • Splay Tree
  • Threaded Binary Tree
  • Segment Tree. Can quickly compute a function over a portion of an array.
  • kd-Tree
  • Heap. A binary tree stored in an array, so it doesn't use pointers. Makes a great priority queue.
  • Fibonacci Heap
  • Trie
  • B-Tree :construction:

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
  • Ordered Set

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!

For more information, check out these great books:

The following books are available for free online:

Other algorithm repositories:

  • EKAlgorithms. A great collection of algorithms in Objective-C.
  • @lorentey. Production-quality Swift implementations of common algorithms and data structures.
  • Rosetta Code. Implementations in pretty much any language you can think of.

License

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

Build Status

Something went wrong with that request. Please try again.