Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentals of Algorithms (Binary search: looks for items in an ordered…
Fundamentals of Algorithms
Algorithm
: a sequence of steps that can be followed to complete a task
be aware that a computer program is an implementation of an algorithm, an algorithm is NOT a computer program
Decomposition
: breaking a problem into a number of sub-problems so that each sub-problem accomplishes an identifiable task, which might itself be further sub-divided
Abstraction
: the process of removing unnecessary detail from a problem
Linear search
: checks each item of the list in turn to see if it's the correct one. It stops when it either finds the item it's looking for, or has checked every item
Advantages
can be used on any type of list, doesn't have to be ordered
much simpler to code
on small ordered lists the difference in efficiency doesn't really matter so the run time of both algorithms will be similar
Disadvantages
binary search run time will generally be much quicker on large lists
Binary search
: looks for items in an ordered list
2) stop if item = found
3) else compare the item you are looking for to the middle item. If item < middle get rid of second half of the list else get rid of first half of list
middle = (n+1)/2 - round up if necessary
1) find the middle item
4) repeat steps 1)-3) - keep going until you find item
Merge sort
STEPS
1) split in half- second half should start at middle
2) repeat step 1) until all the lists only contain one item
3) merge pairs of sub-lists so that each sub-list has twice as many items, when merging sort items into correct order
4) repeat steps 3) until all sub-lists are merged together
Advantages
more efficient and quicker on long lists
very consistent run time regardless of how ordered the list is
Disadvantages
goes through the whole process even if its already sorted
it uses more memory as it has to create additional lists
Bubble sort
Advantages
simple algorithm
efficient to check already ordered lists
doesn't use much memory
STEPS
1) look at first two items
2) if they are in wrong order swap them
3) move onto next pair and repeat step 2)
4) repeat step 3) until you get to the end - the last item will now be incorrect oder so don't include it in the next pass
5) repeat steps 1)-4) until there are no swaps in a pass
Disadvantages
inefficient way to sort a list - worst case scenario would have n(n-1)/2 comparisons
slow run time for large lists