Sorting Algorithms
Bubble Sort
Numbers are sorted into ascending order by comparing pairs of numbers. If the number on the left is larger than the number on the right, the two numbers are swapped. If the number on the right is larger, everything is kept the same.
This process is repeated until the list is completely sorted. In the worst case – where the list is in descending order – there must be n (n being the number of items in the list) – 1 passes.
For the number of comparisons each pass: if the algorithm is straight forward, it will be n-1, but the algorithm could be designed to appreciate that after the first pass, the largest number must be in the correct place, so it can automatically skip this out.
Either way, this means Bubble sort is in Quadratic time: O(n2)
Quick Sort
Quick sort picks a number to be a pivot. It is usually the middle number (the rightmost if there are an even number of items) but it could be any number in the list and there should theoretically be no loss in efficiency. It then iterates through the other numbers, and puts them on the left of the pivot if smaller, right if bigger (order must persist!). Once one iteration is done, a new pivots are picked out of the two sets of numbers either side of the original pivot. The same process is then repeated until all numbers have been the pivot.
The order of quciksort is O(log n) but it seems I don’t need to be able to show it or know it at all.
Graph Theory
A Graph consists of vertices (nodes) and edges (arcs).
A vertex has an order (degree, valency). This is equal to the number of edges that are connected to it.
Network
A network is a graph where every edge has a weight (numbered)
Connected
A connected graph means every vertex has a path to every other vertex
Simple Graph
A simple graph has no loops and no multiple edges
Directed Graph
A directed graph gives a direction to every edge
Complete Graph (kn)
A graph that contains n vertices where each vertex has an edge between every other vertex. There will be
edges.
