Computing#1-Algorithms Flashcards
Computational thinking
3 techniques:
Decomposition-Breaking down a complex problem into smaller problems and solving individually.
Abstraction-picking out important bits of information from the problem and ignoring specific details that don’t matter.
Algorithmic thinking-logical wash of getting from problem to solution. If the steps taken follow an algorithm, they can be used to solve a future problem.
Search algorithms
Binary search-Keeps halving a list until it finds the item its looking for. Eg it looks at the middle item at the start. If the item it’s looking for is on the right side, it will exclude the left side vice versa. It will keep looking at the middle item and excluding halves until it finds the item it’s looking for
Linear search-looks at every item in a list in turn until the end or until it finds the term. Simpler than binary but not as efficient for larger lists.
Bubble Sort
Swaps individual pairs of items. Passes through the algorithm several times until it has sorted the entire algorithm.
Pros of bubble sort
Pros: Simple algorithm, easily implemented on a computer
Efficient way of checking if a list is already in order. (Only one pass is needed)
Doesn’t use much memory.
Cons of bubble sort
Inefficient way of sorting a list.
Slow for large lists of items
Merge sort
Splits list apart into lists that eventually only contain 1 item. Then they are merged together in order, starting with pairs, fours,eights etc until list is sorted. Use common sense if list is odd. The second sub list should start at middle item.
Pros of merge sort
More efficient and quicker that bubble for large lists, similar running time for smaller lists.
Consistent running time no matter how ordered items in the original list are.
Cons of merge sort
If list is already sorted, it still splits and merges, so bubble may be quicker in some cases.
Uses more memory than a bubble sort as it has to create additional lists.
