Paper 2 - Algorithms Flashcards
Decomposition
Breaking down a complex problem into smaller problems and solving each individually
Abstraction
Picking out important parts of the problem and ignoring insignificant details
Algorithmic Thinking
Making logical steps towards a solution.
Sub Routine
sub programs referenced in a flow chart.
Bubble Sort Algorithm - What is it?
Swaps order of items if they’re in the wrong order.
Bubble Sort Algorithm - Pros and cons?
Pros: Simple, efficient to see if a list is in order and doesn’t use much energy
Cons: Inefficient way to sort a list, can’t cope with a very large list
Linear search: What is it?
Checks each item of a list to see if it’s the correct one
Linear Search: Pros and cons?
Simple and not as efficient as binary search. Used for smaller lists. Can be used on any type of list.
Binary Search: What is it?
Finds middle item in list, if the item i not what you’re looking for you compare it with the desired variable and discern if it is after or before in the list. Then you get rid of half the list and compare the desired variable with the middle item; Continue this until you find the desired item.
Merge Sort: What is it?
Splits the list into smaller sub lists, the second starting from the middle item; repeat this until all the lists contain one item and merge pairs of sub-lists with items sorted in order; repeat this until all the sub lists are together.
Merge Sort: Pros and Cons?
Pros: more efficient, quicker for large lists and has a consistent running time.
Insertion Sort: What is it?
It’s the simplest sorting algorithm; It compares each item to every other item in a list and insert them in the right place.
Insertion Sort: Pros and Cons?
Pros: Intuitive, easily coded, Good for small lists, doesn’t require much memory, quick if adding items to an ordered list, very good at checking if a list is already sorted.
Disadvantage: Doesn’t cope well with large lists.
