Swift Algorithm

- June 08, 2016

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.
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!):

Bubble Sort

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.

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

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

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. 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
All-Pairs Shortest Paths

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.

iOS Helper