Macs in Chemistry

Insanely Great Science

Swift Algorithm Club

 

The Swift Algorithm Club is a new site that described implementations of popular algorithms and data structures in Swift. However there is also an added bonus in that there are also detailed explanations of how they work. The list below gives an idea of what is available or under construction, and I’m sure they would be delighted to receive contributions.

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

  • Insertion Sort
  • Selection Sort
  • Shell Sort

Fast sorts:

  • Quicksort
  • Merge Sort
  • Heap Sort

Special-purpose sorts:

  • Counting Sort
  • Radix Sort
  • Topological Sort

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.
  • Comb Sort. An improve upon the Bubble Sort algorithm.

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

blog comments powered by Disqus