Algorithms 2.1 Searches and sorts Flashcards
Describe the steps a binary search will follow to look for a number in a sorted list
Find the middle item in the ordered list.
check if selected number is equal to / matches target number
if this is the item you are looking for, then stop the search - since the number has been found
if this item is not equal to the target item then check:
if searched number is larger, then discard left half
if searched number is smaller, then discard right half
Repeat this process until the number or item is found or
remaining list is of size 1 / 0 (which shows number was not found/ or number was not in list)
there are no more items to be found (remaining list is of size 1 or 0)
Examples of Standard searching algorithms:
Binary search
Linear search
What are binary search and linear search examples of
Examples of Standard searching algorithms:
Use the binary search algorithm to find he number 8 in the following list
3 6 8 11 13 15 18
Middle item = (7 + 1) /2 = 4th item
4th item = 11
compare 11 to 8
11 > 8 so split left
Items in list: 3,6,8
Middle item = (3+1)/2 = 2nd item = 6
compare 6 to 8
6 < 8 so split right
Items in the list: 8
8 is the last item in the list
Middle item = (1+1)/2 = 1st item = 8
Stop searching as 8 has been found
Show the stages of a binary search to find the word ‘zebra’ when applied to the data shown
amber, house, kick, moose, orange, range, tent, wind, zebra
middle item = (9 + 1) / 2 = 5th item
5th item = orange
compare zebra to orange
zebra > orange, so split right
middle item = (4+1)/2 = 2.5 rounds up to 3rd item
3rd item = Wind
compare zebra to wind
zebra>wind, so split right
Zebra is the last item in the list OR Middle item = (1+1)/2 = 1st item = Zebra
Compare zebra to zebra
Zebra = Zebra
Item has been found
Middle item = (1+1)/2 = 1st item = Zebra
Describe the steps a linear search would follow when searching for a number that is not in the given list.
Starting with the first value
Checking all values in order
Describe the steps a linear search
1) look at the first item in the unordered list
2) is this is the item you are looking for, then stop the search - the item has been found
3) if not, then look at the next item in the list
repeat steps 2) - 3) until you find the item that you are looking for or you have checked every item (this shows that the item was not in the list)
Use linear search to find “11” in the list
3 6 8 11 13 15 18
Starting with the first value
Check each item in order:
Check 1st item: 3 ≠ 11 move to the next item in the list
Check 2nd item: 6 ≠ 11 move to the next item in the list
Check 3rd item: 8 ≠ 11 move to the next item in the list
Check 4th item: 11 = 11
Stop searching as 11 has been found
Nicoa has a list of numbers
2 3 7 5 13 11
She says, “I can’t use a binary search to find 13” Why is this the case
A binary search only works on ordered data
file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf
file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf
Standard sorting algorithms:
o Bubble sort
o Merge sort
o Insertion sort
o Bubble sort
o Merge sort
o Insertion sort
are examples of
Standard sorting algorithms
Merge sort is an example of ______
divide and conquer algorithm
describe the steps to bubble sort
1)look at the first two items in the list
2) if they are in the right order, you dont have to do anything
If they are in the wrong order, swap them
3) move on to the next pair of items (the 2nd and 3rd items) and repeat step 2).
4) repeat step 3) until you get to the end of the list - this is called one pass
The last item will now be in the correct place, so dont include it in the next pass
5) Repeat steps 1) - 4) until there are no swaps in a pass
describe the steps to merge sort
1) split the list in half (the smaller lists are called sub lists) - the second sub-list should start at the middle item
2) keep repeating step 1) on each sub-list until all the lists only contain one item
3) merge pairs of sub-lists so that each sub-list has twice as many items
Each time you merge sub-lists, sort the items into the right order
describe the steps to insertion sort
1) Look at the second item in a list
2) Compare it to all items before it (in this case just the first item) and insert the number into the right place
3) Repeat step 2) for the third, fourth, fifth etc. items until the last number/item in the list has been inserted into the correct place
advantages of linear search
much simpler than binary search
can be used on any type of list
daya doesn’t have to be order
used on small lists
disadvantages of linear search
not as efficient as binary search
adv. of binary search
much more efficient than a linear search (once the list has been ordered)
in general binary search takes fewer steps to find the item you are looking for - which makes it more suitable for large lists of items
disadv. of binary search
data has to be order before a specific item can be searched
adv. of bubble sort
simple algorithm - can be easily implemented on a computer
an efficient way to check if a list is already in order
doesn’t use very much memory as all the sorting is done in the original list
disadv. of bubble sort
it is an inefficient way to sort a list
due to being inefficient, the bubble sort algorithm does not cope well with a very large list of items
adv. of merge sort
in general, more efficient and quicker than bubble sort and insertion sort algorithms for large lists
it has a very consistent running time regardless of how ordered the items in the list are
disav. of merge sort
it is slower than other algorithms for small lists
even if the list is already sorted, it still goes through the whole splitting and merging process
it uses more memory than the other sorting algorithms (bubble and insertion sort) in order to create the separate lists
adv. of insertion sort
it is an intuitive way of sorting things and can be coded
it copes very well with small lists - for this reason, an insertion/merge hybrid sort is often used to take advantage of the strengths of each algorithm
all the sorting is done on the original list so, like bubble sort, it doesn’t require very much additional memory
it is very quick to add items to an already ordered list
it is also very quick in checking that a list is already sorted
disadv. of insertion sort
it doesn’t cope well with very large lists
