Minimum spanning tree

Finding MST using Kruskal's algorithm

Another algorithm for finding the MSP is Prim's algorithm.
There are cases where there might be more than one possible minimum spanning tree

Topological Stuff

Here's a quick and simple algorithm for topological ordering:
(examples to follow)

• Find a node with NO incoming edges, and order it first.
• Delete that node from the graph.
• Repeat.

Source:

• http://www.cs.umd.edu/class/sum2005/cmsc451/topology.pdf
• http://homes.cs.washington.edu/~jrl/421slides/lec5.pdf

Insertion Sort

wikipedia link

Selection Sort

"Red is current min.
Yellow is sorted list.
Blue is current item."
~Wikipedia

So blue iterates through the list, comparing values as it goes along. The current minimum value is stored in red. By the time the end of the list is reached (with blue), the value that is red at that time, will be the smallest value in the "active part" of the list.
It is moved to the end of the "passive section", marked in yellow. Once it is yellow, it doesn't need to search it again, as it's already where it should be.

Please note: The algorithm doesn't really use colours. They are just for visualisation.

"Selection sort" because it selects the smallest value and works with that.

wikipedia link

Bubble Sort

wikipedia link

Counting Sort

COUNTING SORT VISUALISATION HERE!!!

General Sorting Stuff

	Best case	Average Case	Worst Case
Quick Sort	O(n log(n))	O(n log(n))	O(n²)
Merge Sort	O(n log(n))	O(n log(n))	O(n log(n))
Insertion Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Bubble Sort	O(n)	O(n²)	O(n²)

Found here: http://bigocheatsheet.com/

Fancy visualisation

Less fancy, but still useful visualisations

Quick 'n easy bits o' code  <- Quick explanation of some sorting algorithms