Search
Search

10 Algorithms Every Programmer Should Know – and When to Use Them

Bubble sort

Use it when…

How it works:

You have a list of things that are mostly in order, with a few that need to be put in order, OR you have a very small list of things to put in order. Compare every item in the list with every other item, and if they’re in the wrong order, swap them.

Merge sort

Use it when…

How it works:

You have a list of things on disk, or other “slow storage” that need to be in order, but aren’t. Break the list into two lists. Then break each of those into two lists, etc… until each list is only 1 or 2 items. If the two things in those tiny lists aren’t in order, swap them. Then combine two tiny lists together in order, then combine those lists together in order, etc… until you’re left with one list that’s in order.

Quick sort

Use it when…

How it works:

You have a list of things in memory that need to be sorted, but aren’t. Pick an item in the list to be the “pivot.” Put all the items that are less than the pivot on one side of the pivot, and all the other items on the other side. Then break the list into two smaller lists at the pivot. Repeat for each smaller list. Once all the lists have only one item, combine them back together and they’re in order.

Linear search

Use it when…

How it works:

You have a list of things that aren’t in order, and you need to find one of them. Look at each item in the list, starting at the first, until you find the one you want.

Binary search

Use it when…

How it works:

You have a list of things that are in order, and you need to find one of them. Look at the middle item in the list. If it’s your item, then you’re done! Otherwise, take the half-list where your item would be and repeat by finding the middle item of that half-list. Repeat until you find the item, (or there are no half-lists left, in which case your item isn’t there).

Tree traversal

Use it when…

How it works:

You have a “tree” of data, and you need to look at all the nodes in the tree. Start with the “root” of the tree. Do what you need to with it, then look at each of its children. Repeat with each child as if it was the root.

Dijkstra’s algorithm

Use it when…

How it works:

You have a bunch of “places” and “paths”, and need to find the shortest path between two places. Make a list of all the places. Beginning at your ending place, put a “1” next to each place that’s connected to the ending place by a path. Then, for each of those places, do the same, but this time put a “2”. Continue looking at each place and all the places it can get to, putting the number that indicates how far it is from the ending place by adding 1 to the connected place’s distance. If a place already has a number, you replace it if the new number would be smaller. When you’ve looked at all the places, the path from the starting place to the ending place will follow the smallest numbers.

Powerset construction

Use it when…

How it works:

You have a “state machine” that can’t decide which state it should move to next. Each ambigious state transition gets its own miniature state machine that removes the ambiguity

Monte Carlo method

Use it when…

How it works:

You need an answer from a set of data, but there is too much data to process efficiently. Randomly choose from a carefully constructed subset of the data, and extract your answer from that subset

Reference counted garbage collection

Use it when…

How it works:

You probably won’t ever have to write code to do this, but if your programming language takes care of memory management for you, you should know how it works. Every object knows how many other objects are linked to it. When that number is 0, that object disappears from memory.