Algorithms 2.1 Searches and sorts

Question 1

Describe the steps a binary search will follow to look for a number in a sorted list

Answer 1

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)

Question 2

Examples of Standard searching algorithms:

Answer 2

Binary search
Linear search

Question 3

What are binary search and linear search examples of

Answer 3

Examples of Standard searching algorithms:

Question 4

Use the binary search algorithm to find he number 8 in the following list
3 6 8 11 13 15 18

Answer 4

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

Question 5

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

Answer 5

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

Question 6

Describe the steps a linear search would follow when searching for a number that is not in the given list.

Answer 6

Starting with the first value
Checking all values in order

Question 7

Describe the steps a linear search

Answer 7

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)

Question 8

Use linear search to find “11” in the list
3 6 8 11 13 15 18

Answer 8

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

Question 9

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

Answer 9

A binary search only works on ordered data

Question 10

file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf

Answer 10

file:///C:/Users/44748/Documents/The%20code%20for%20all%20the%20searching%20and%20sorting%20algorithms.pdf

Question 11

Standard sorting algorithms:

Answer 11

o Bubble sort
o Merge sort
o Insertion sort

Question 12

o Bubble sort
o Merge sort
o Insertion sort

are examples of

Answer 12

Standard sorting algorithms

Question 13

Merge sort is an example of ______

Answer 13

divide and conquer algorithm

Question 14

describe the steps to bubble sort

Answer 14

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

Question 15

describe the steps to merge sort

Answer 15

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

Question 16

describe the steps to insertion sort

Answer 16

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

Question 17

advantages of linear search

Answer 17

much simpler than binary search
can be used on any type of list
daya doesn’t have to be order
used on small lists

Question 18

disadvantages of linear search

Answer 18

not as efficient as binary search

Question 19

adv. of binary search

Answer 19

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

Question 20

disadv. of binary search

Answer 20

data has to be order before a specific item can be searched

Question 21

adv. of bubble sort

Answer 21

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

Question 22

disadv. of bubble sort

Answer 22

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

Question 23

adv. of merge sort

Answer 23

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

Question 24

disav. of merge sort

Answer 24

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

Question 25

adv. of insertion sort

Answer 25

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

Question 26

disadv. of insertion sort

Answer 26

it doesn’t cope well with very large lists