algorithms Flashcards
what is abstraction
the process of removing unnecessary details and including only relevant details
what does decomposition mean
breaking a complex problem down into smaller more manageable parts
what is a binary search (explain in-depth)
1) calculate midpoint in data set
2) check if that is the item to be found :
if not
3)if the item to be found is lower than the midpoint, repeat on the left half of the data set
4)if the item to be found is greater than the mid-point, repeat on the right half of the data set
5) repeat until the item is found or there are no items left to check
what does a binary search require
requires items to be in order
what does a binary search require
requires items to be in order
binary search is better because
its faster/more efficient
what does a linear search not require?
the data set to be in order
what does a linear search do (in depth)
starts from the beginning of a data set, each item is checked in turn to see if it is the one being searched for
bubble sort does what…(in depth)
it sorts an unordered list of items
compares each item with the next one and swaps them if they are out of order
the algo finishes when no more swaps need to be made
(it bubbles up the largest/smallest item to the end of the list
it is the most inefficient sorting algo but easiest to implement
popular for small data sets
bubble sort example (very long winded)
smallest to largest
6,4,5,2,3,1
first, check 6 and 4, 4 is smaller than 6 so swap places
4,6,5,2,3,1
now check 6 and 5, 5 is smaller so swap
4,5,6,2,3,1
now check 6 and 2, 2 is smaller so swap
4,5,2,6,3,1
check 6 n 3, 3 is smaller
4,5,2,3,6,1
check 6 and 1, 1 smaller
4,5,2,3,1,6
first pass done, but 6 is at the end, so 2nd pass needed
4,5,2,3,1,6
4,2,5,3,1,6
4,2,3,5,1,6
4,2,3,1,5,6
2nd pass done
3rd pass, we ignore 5 and as they are sorted
4,2,3,1,5,6
2,4,3,1,5,6
2,3,4,1,5,6
2,3,1,4,5,6
4th pass, ignore 4 5 6
2,3,1,4,5,6
2,1,3,4,5,6
5th
2,1,3,4,5,6
now all we need to do is swap 2 and 1
1.2.3.4.5.6
this is bubble sort.
insertion sort
the insertion sort inserts each item into its correct position in a data set one at a time
it is useful for small data sets
useful for insertings items into an already sorted list
usually replaced by more efficient sorting algorithms for large data sets
merge sort
creates two or more identical sub problems from the largest problem and solves them individually
combines their solutions to solve the bigger problem
data set repeatedly split in half
until each item is in its own list
adjacent lists are then merged back together
