2.1 Algorithms Flashcards
(16 cards)
What are the steps of a linear search?
Check the first value
IF it is the value you are looking for Celebrate and stop
ELSE move to and check the next value
REPEAT UNTIL you have checked all the
elements and not found the value you are
looking for
What are the pros of linear searching?
Performs well with small and medium sized lists
Fairly simple to code
Data doesn’t need to be in any particular order
Doesn’t break if new items are added into the list
What are the cons of linear searching?
May be too slow to process large lists
If you are searching for the last item in a list, you may have to go through the whole list
What are the steps of a binary search?
List first needs to be sorted into order.
take the middle value.
Compare to the value you are looking for.
IF it is the value you are looking for, celebrate and stop
ELSEIF it is larger than the value you are looking for, take the values to the left of the middle value and find the middle again
IF it is smaller than the one you are looking for, take the values from the right of the middle value and find the middle again
How do you find the index of the midpoint of an array?
LP (Left point) + RP (Right point) DIV 2
What are the pros of a binary search?
Very good performance over large ordered lists.
Takes a maximum of 8 loops to find an item in a list of 1000 items.
What are the cons of a binary search?
Only works on ordered lists.
More complicated than a linear search to code.
If new items are added to the list it will need reordering every time they are added.
What are the steps to complete a bubble sort?
Take the first element and the second element from the list.
Compare them.
IF element 1 > element 2 THEN, swap item
ELSE, do nothing
REPEAT: move along the list to the next pair
IF no more elements: Go to 1
ELSE: Go to 2
UNTIL: you have moved through the entire list and not made any changes
What are the pros of using a bubble sort?
Simple to write
Simple to understand
Data is sorted in the same Memory location that it is held.
What are the cons of using a bubble sort?
One of the slowest ways to sort a list.
What are the steps of completing a merge sort?
Split all elements up into individual lists
Compare the first adjacent element in both lists
Put the smallest into a new list
Compare the next element of 1 list with the second element of the second list
Put the smallest into a new list
Repeat until merged
What are the pros of a merge sort?
It is the fastest of the three types of sort (bubble, insert, merge)
It is the best option to use for long lists of data (more than 1000 long)
What are the cons of a merge sort?
More complicated to code compared to bubble and insert
It may use twice the memory size of the list - depending on the way it is coded
What are the steps of an insertion sort?
the elements are an unsorted list
Compare the 1st element in the unsorted list to the next element in the sorted list
IF it is smaller, swap it by moving the element to the left
ELSE IF there are no elements in the unsorted list put it in the final position
REPEAT UNTIL all element in the unsorted list are in the sorted list
What are the pros of an insertion sort?
Easy to implement / code
Memory efficient
good for small or nearly sorted lists
What are the cons of an insertion sort?
Inefficient for large datasets
Not suitable for high-volume data
Can be slower than other algorithms
