section 5 - algorithms Flashcards
the beginning and the end of the algorithm are put in boxes with rounded corners - they are sometimes called terminals
anything that’s put into or taken out of the algorithm goes into a parallelogram box
general instructions processes and calculations go into rectangular boxes
decisions often yes and no questions are put into diamond boxes
sub programmes reference other flow charts
arrows connect boxes and show the direction you should follow some boxes might have multiple Arrows coming in or going out of them
flowcharts
can show sequences, selections, iterations or a combination of them
sequence flowchart to calculate salary of worker after 10% pay increase
selections flowchart to check if a password is valid - has more than six characters & is different from the username
iterations flowchart - linear search
binary search
1) Find the middle item in the ordered list - in a list of n items do (n + 1) ÷ 2
and round up if necessary to find middle item
2) If this is the item you’re looking for, then stop the search you’ve found it.
3) If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list.
4) You’ll be left with a list that is half the size of the original list. Repeat steps 1) - 3) on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.
binary search example
Use the binary search algorithm to find the number 99 in the following list.
7, 21, 52, 59, 68, 92, 94, 99, 133
There are 9 items in the list so the middle item is the (9+1) ÷ 2 = 5th item. The 5th item is 68 and 68 < 99 so get rid of the first half of the list to leave:
92, 94, 99, 133
There are 4 items in the list so the middle item is the (4+1) ÷ 2 = 3th item (rounded up). The 3th item is 99
Linear Search
1) Look at the first item in the unordered list.
2) If this is the item you’re looking for, then stop the search - you’ve found it.
3) If not, then look at the next item in the list.
4) Repeat steps 2) - 3) until you find the item that you’re looking for or you’ve checked every item
linear search example
7, 21, 52, 9, 68, 92, 94, 99, 133
linear vs binary search
A linear search is much simpler than a binary search but not as efficient. A linear search can be used on any type of list, it doesn’t have to be ordered. Due to it being inefficient, a linear search is often only used on small lists.
Once the list has been ordered, a binary search is much more efficient than a linear search. In general a binary search takes fewer steps to find the item you’re looking for, which makes it more suitable for large lists of items.
Bubble sort
1) Look at the first two items in the list.
2) If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.
3) Move on to the next pair of items (the 2nd and 3rd entries) and repeat step 2). 4) Repeat step 3) until you get to the end of the list this is called one pass. The last item will now be in the correct place, so don’t include it in the next pass.
5) Repeat steps 1) - 4) until there are no swaps in a pass.
bubble sort example
Merge Sort
1) Split the list in half (the smaller lists are called sub-lists) the second sub-list should start at the middle item (see p.69).
2) Keep repeating step 1) on each sub-list until all the lists only contain one item. 3) Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order.
4) Repeat step 3) until you’ve merged all the sub-lists together.
Merge Sort example
bubble sort pros
- It’s a simple algorithm that can be easily implemented on a computer.
- It’s an efficient way to check if a list is already in order. For a list of n items you only have to do one pass of n - 1 comparisons to check if the list is ordered or not.
- Doesn’t use very much memory as all the sorting is done using the original list.
bubble sort cons
- It’s an inefficient way to sort a list - for a list of n items, the worst case scenario would involve you doing n(n-1) / 2 comparisons
- Due to being inefficient, the bubble sort algorithm does not cope well well with a very large list of items.
merge sort pros
- In general it’s much more efficient and quicker than the bubble sort (p.70) and insertion sort algorithms (p.72) for large lists.
- It has a very consistent running time regardless of how ordered the items in the original list are.
merge sort cons
- It’s slower than other algorithms for small lists.
- Even if the list is already sorted it still goes through the whole splitting and merging proces
- It uses more memory than the other sorting algorithms in order to create the separate lists.
insertion sort
1) Look at the second item in a list.
2) Compare it to all items before it and insert the number into the right place.
3) Repeat step 2) for the third, fourth, fifth, etc. items until the
last number in the list has been inserted into the correct place