section 4 algorithms Flashcards
what is decomposition
breaking a complex problem down into smaller problems and solving each one individually
what is abstraction
picking out the important bits of information from the problem, ignoring the specific details that don’t matter
what is 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
what is pseudocode
not an actual programming language but is should follow a similar structure and read like one
it’s quick to write and can be easily converted
how do you use a binary search
1) find the middle item
2) if not the right item compare it with the middle item
3) if it comes before the middle item get rid of the second part and vise verses
4) you’ll be left with half the list and you repeat until you find the item
how do you use linear search
1) look at first item
2) if not the right item look at the next one in the list
3) continue until you find the item
linear Vs binary search
linear is simpler binary is more efficient linear can be used on any list linear is mostly used on small lists binary is mostly used on large lists
how does bubble sort work
1) look at first two items
2) if they are in the wrong order swap them
3) repeat until you get to the end of the list(pass)
4) repeat until there are no swaps in a pass
advantages of bubble sort
simple
efficient way to check if the list is ordered
not much memory
disadvantages of bubble sort
inefficient way to sort a list
does not cope with large lists
how does merge sort work
1) split list in half
2) keep splitting until each sub list contains one item
3) merge pairs of sub lists and each time order it
4) repeat until you’ve merged all the sub lists
advantages of merge sort
more efficient than bubble and insertion
consistent running time
disadvantages of merge sort
slower on small lists
more memory
has to go through merging even if ordered
how does insertion sort work
1) look at second item
2) compare with items before and insert the number into the right place
3) repeat until last number has been inserted
advantages of insertion sort
intuitive way and can be easily coded
copes well with small lists
doesn’t require additional memory
quick at cheeking if in order
