Decomposition
Breaking a complex problem down into smaller problems and solving each one individually
Algorithmic thinking
A logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future.
Abstraction
Picking the important bits of information from the problem, ignoring the specific details that don’t matter
Binary search
Keep comparing with the middle item in an ordered list
Linear search
Check each item of a list in turn to see if it’s the correct one
Linear vs binary search
Linear search is much simpler, but not as efficient. Linear can be used on any type of list, doesn’t have to be ordered. Binary is more suitable for a large list.
Bubble sort
- look the first two items on the list
- If they’re in the wrong order, swap
- Do the same for the next pair of items, until the end of the list
- Repeat until there are no swaps in a pass
Bubble sort pros
- simple algorithm
- efficient way to check if a list is a;ready in order
- doesn’t use very much memory (all sorting is done using the og list)
Bubble sort cons
- inefficient
- doesn’t cope w very large lists
Merge sort pros
- more efficient than bubble sort
- consistent running time
Merge sort cons
- Slower for small lists
- goes through whole process even if list is sorted
- uses more memory
Incersion sort (orders the items as it goes)
- look at the second item in a list
- compare to all items before it and insert the number into the right place
- Repeat until the last number in the list has been inserted into the correct place
