Algorithms

Finds the middle element in a list of data before deciding which side of the data the desired element is to be found in. The unwanted half of the data is then discarded, and the process is repeated until the desired element is found or until it is known that the desired element doesn’t exist in the data.

The list must have been sorted already

You can think of it as going along a bookshelf one by one until you come across the book you’re looking for. Sometimes the algorithm gets lucky and finds the desired element almost immediately, while in other situations, the algorithm is incredibly inefficient.

Left right root

from top to bottom, left to right

The bubble sort algorithm works by repeatedly going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order. Each time the algorithm goes through the list, it is called a pass and on the final pass, it checks to see if any swaps are needed, if not the list must be sorted.

The insertion sort algorithm works by building up a sorted sub list in the first part of the original list, while the remaining part of the list remains unsorted At the start of the algorithm, the sorted sub list contains just a single item (the first item in the list). All of the other items belong to the unsorted sub list. The algorithm goes through the unsorted sub list, item by item. As each item is examined, it is moved into the correct position (in ascending or descending order) in the sorted sub list. This progresses until the final item is correctly inserted and the list is sorted

On large lists, as it usually requires less comparisons per pass making it quicker and more efficient

A stack is a type of FILO data structure, using a pointer to point to the element currently at the top of the stack

A queue is a type of FIFO data structure, using two pointers. A front pointer to points to the first element in the queue and a back pointer which points to the next empty space at the back of the queue

Similarity: Both are often implemented as arrays Difference: stacks use 1 pointer, queues use 2

Add: enqueue(elementName) remove: dequeue()

Add: push(elementName) remove: pop()

The pointer decrements by 1, pointing to the element below

The front pointer incremented by 1, pointing to the next element in the list The back pointer remains unchanged

The stack or queue has to be checked to see if its empty, if not then an element can be removed

The back pointer increments by one

Time complexity is the amount of time it takes an algorithm to solve a particular problem

The amount of time taken to complete an algorithm is independent from the number of elements inputted O(1)

The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted O(n)

The amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted O(n^2)

The amount of time taken to complete an algorithm will double with every additional item O(2^n)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted

Space complexity is the amount of storage the algorithm takes up