Here’s the concepts covered this week:
- Algorithm – Basically some amount of logic and functionality with the intent of solving a particular problem. The solution to a particular problem , may be one or more algorithms, grouped or abstracted into 1 or more functions within a computer program. Typically, an algorithm will take some input, perform some logic and produce some output.
- Running Time – Denoted as example – O(n) to denote the running time of a program based on n number of steps (decisions and / or problems to solve or some combination). Graphed with time on y axis, size of problem on the x axis.
- Search
- Linear Search – Algorithm searching a list of data 1 by 1. Running time O(n).
- Binary Search – Assumes a list of data is sorted. Then does a search starting in the middle of the list. Depending on first decision, the algorithm discards the other half of the list and then repeats the steps with the remaining half. More efficient than linear search. Running time O(log n).
- Sort
- Selection – Find the smallest element in remaining list, swap the smallest element with the first and iterate. Repeat.
- Bubble – Iterate through remaining list and swap pairs of elements if they are out of order. Repeat.
- Merge sort – Introduced after recursion – as a more efficient sorting algorithm in which 1 half of the set is sorted, the other half is sorted and then the results combined. Apparently, this is more efficient.
- Here’s a great animation of the sorting algorithms.
- Recursion – A technique where a function can call itself, the function repeating ”recursively” until some decision/test causes it to stop. Can be used for coding efficient searching and sorting algorithms.
