Decision Maths 1 Revision

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.

C# Sharp exercises: Bubble sort - w3resource

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.

Formula for number of comparisons with n being number of items in list

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.


How to normalize edges weight between 0 and 1 - Mathematics Stack Exchange

A network is a graph where every edge has a weight (numbered)


A connected graph means every vertex has a path to every other vertex

3. The graph shown is an example of disconnected graph with three... |  Download Scientific Diagram
Disconnected Graph

Simple Graph

A simple graph has no loops and no multiple edges

Simple Graph -- from Wolfram MathWorld

Directed Graph

Directed graph - Wikipedia
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


Song of the article