Common Algorithms Finished Flashcards
what are the searching algorithms (2)
linear
binary
what are the sorting algorithms (3)
bubble
merge
insertion
describe the steps of a linear search (6)
find the length of the data set
set counter to 0
examine value held in the list at the counter position
check to see if the value at the counter position matches the value searched for
if it matches, end the search
if not, increase the counter by 1 and search again
1 adv and 1 disadv of linear search
+ works on any data set (doesn’t have to be sorted)
- can be slow on larger data sets
describe the steps of a binary search (5)
start by setting the counter to the middle position in the list
if the value is a match, stop
if the value at the midpoint is less than the desired value, the list is divided in half and the lower half of the list is ignored
otherwise, the upper half of the list is ignored
the search continues for the remaining items
what happens in a binary search of the mid point value is a decimal
round up
1 adv and 1 disadv of binary search
+ much more efficient than linear on longer data sets
- the list needs to be sorted
describe the steps of bubble sort (5)
start at the beginning of the list
compare the first value in the list with the next one up. if the first value is bigger, swap the position of the two values
move to the second value in the list. compare them again and swap if the value is bigger
keep going until there are no more items to compare
go back to the start of the list and go again
describe the steps of a merge sort (2)
the list is repeatedly divided into two until all the elements are in groups of two
pairs of elements are compared, placed into order and combined until the list is ordered
describe the steps of an insertion sort
values in a list are compared in turn, starting with the second value
if this value is greater than the value to the left of it, no changes are made
otherwise, that value is repeatedly moved left until this is true
