Algorithms Flashcards
Flowchart symbols
curved rectangle = start/end
rectangle = instruction
diamond = decision
linked by arrowed lines
Bubble sort
compare adjacent terms
1) start at beginning of the list. Pass through the list and compare adjacent values. For each pair of values:
- if they are in order, leave them
- if they are not in order, swap them
2) when you get to the end of the list, repeat step 1
3) when a pass is completed without any swap,s the list is in order
Algorithm =
a defined, finite sequence of instructions used to solve a problem
Quick sort algorithm
- select pivots and split items into sub-lists
1) choose the item at the midpoint of the list to be the first point (round up 0.5(n+1) so right if even)
2) Write down all the items that are less than the pivot in a sublist whilst keeping their order
3) Write down/add the pivot
4) Wrote down the remaining items (those greater than the pivot) in a sublist
5) Apply steps 1 to 4 to each sublist
6) when all items have been chosen as pivots, stop
Points on quick sort
Number of pivots could double at each path. 2^(n-1) n paths
Points on bubble sort
Maximum number of passes = n-1 as after each pass you exclude a number from the end
Max number of swaps/comparisons = 0.5n(n-1) as first pass has (n-1) comparisons and final pass has (n-(n-1)) comparisons
Compare the relative efficiency of sorting algorithms by
comparing the number of comparisons and swaps that are made to sort the same list of numbers
First fit decreasing algorithm
place items in the first possible bin from largest to smallest item
Full bin packing algorithm
find combinations of items that will fill a bin
any remaining items are packed using the first fit algorithm
Pro and con of full bin algorithm
pro: usually a good solution
con: large numbers make it difficult to do
Con of first fit decreasing algorithm
must be sorted first before first fit algorithm applied so requires more computation
