Searching and sorting Flashcards
what are the 2 search methods
linear
binary
how does linear search work
goes through each item in the list and checks to see if it is the right one
how does binary search work
finds the middle item in the list
checks if it is the item
compare to see if the item you are looking for is higher or lower than the middle item
remove the unused half of the list
repeat process
what are 3 benefits of linear search
simpler
does not need to be sorted
works well on small lists
what is a disadvantage of linear search
not as efficient
what are 2 advantages of binary search
efficient
work well on large lists
what are 2 disadvantages of binary search
require list to be sorted
more complex
what are the 3 sorting algorithms in order of efficiency
bubble
insertion
merge
how does bubble sort work
look at 2 items at a time, and will swap them if they are in the wrong order. will keep doing this process until there is a pass that has no swaps
what are the 2 pros of bubble sort
it’s simple
doesn’t use a lot of memory as sorting is done using the original list
what is a cons of bubble sort
inefficient and slow
how does merge sort work
keep splitting a large list until a lot of sublists with 1 item in each are made
merge and order the sublists back together until you have one list
what are 1 pros of merge sort
very quick and efficient
what are 3 cons of merge sort
slower for small lists
uses a lot of memory
complex
how does insertion sort work
goes through each item and puts them in the right place using the first item in the list as a starting point
