Searches And Sorts (Ch5) (M2)

Question 1

What is a linear search?

Answer 1

A linear search is an algorithm used to perform a search for data in a set of data items. It involves sequentially searching through a list from start to finish comparing values.

Question 2

Describe the process of a linear search

Answer 2

Process of a linear search:

1. Find out the length of the data set
2. Set the counter to 0
3. Look at the first item in the unordered list
4. Check to see if the value at that position matches the value searched for
5. If it matches, the value is found. End the search.
6. If not, increment the counter by 1 and go back to step 3 until there are no more items to search.

Question 3

What is a disadvantage of a linear search?

Answer 3

A linear search can be quite inefficient. Suppose the data set contained 100 items of data, and the item searched for happens to be the last item in the set?
All of the previous 99 items would have to be searched through first.

Question 4

What is an advantage of a linear search?

Answer 4

The linear searches will work on any data set, whether it is ordered or unordered

Question 5

Perform a linear search for ‘7’ in the list 2, 5, 8, 7, 4, 3

Answer 5

2 != 7 Not found, go to next index

5 != 7 Not found, go to next index

8 != 7 Not found, go to next index

7 == 7, Value found at position 3

Question 6

What is a binary search?

Answer 6

A binary search is a more efficient algorithm used to perform a search for data in a set of data items.
It involves a divide and conquer technique using mid points to repeatedly split the data set in half and discard items where the search item cannot be located.

Question 7

Describe the process of a binary search

Answer 7

Process of a binary search:

1. Find the middle item in the ordered list
2. If the value is a match, the search ends.
3. If the value at the midpoint is less than the value to be found, the list is divided in half. The lower half of the list is ignored and the search keeps to the upper half of the list.
4. Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
5. The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.

Question 8

Give an advantage of a binary search

Answer 8

A binary search is a much more efficient algorithm than a linear search.
In an ordered list of every number from 0 to 100, a linear search would take 99 steps to find the value 99.
A binary search would only require seven steps.

Question 9

Give a disadvantage of a binary search

Answer 9

A binary search can only work if a list is ordered

Question 10

Complete a binary search for the value 11:

0 1 2 3 4 5 6 7 8
1, 3, 4, 5, 7, 9, 11, 14, 16

Answer 10

The midpoint is found by adding the lowest position to the highest position and dividing by 2.
(8 + 0) / 2 = 4

Check position 4, which has the value 7.
7 is less than 11, so the bottom half of the list (including the midpoint) is discarded.

5 6 7 8
9, 11, 14, 16

The new lowest position is 5.
(8 + 5) / 2 = 6.5, which rounds up to 7.
Position 7 has the value 14, which is greater than 11.
So the top half of the list (including the midpoint) is discarded.

5 6
9, 11

The new highest position is 6.
(6 + 5) / 2 = 5.5, which rounds up to 6.
Position 6 has the value 11, which is a match, so the search ends.

Question 11

Demonstrate a binary search for the value “Bryan” with the following list:

Bryan, Nick, Philip, Robert, Sam, Thomas

Answer 11

0 1 2 3 4 5
Bryan, Nick, Philip, Robert, Sam, Thomas

(0 + 5) / 2 = 2.5, which rounds to 3.
The right side doesn’t contain Bryan, so those values including the midpoint are discarded.

0 1 2
Bryan, Nick, Philip

(0 + 2) / 2 = 1
The right side doesn’t contain Bryan, so that value and the midpoint are discarded.

Bryan is the only value left, output Bryan found at index 0.

Question 12

What is a bubble sort?

Answer 12

A bubble sort is an algorithm that is used to sort a dataset of values by means of repeatedly comparing adjacent pairs of values and swapping items into the correct order

Question 13

Describe the process of a bubble sort

Answer 13

Process of a bubble sort:

1) (Work from left to right)
2) Look at the first two items in the list
3) If element 1 is bigger than element 2, then swap them around
4) Otherwise, do nothing
5) Repeat this for the next elements in the list (2 and 3 and 4, then 4 and 5, etc)
6) If there are no elements left, then you have completed a pass. Then start back at the beginning of the list and repeat again.

Question 14

Give a disadvantage of the bubble sort

Answer 14

Disadvantages:
It is the slowest to execute
It is an inefficient way to sort a list
Due to it being inefficient, the bubble sort algorithm does not cope well with a large list of items

Question 15

Give an advantage of the bubble sort

Answer 15

Advantages:
It is a simple algorithm that can be easily implemented on a computer
It’s an efficient way to check if a list is already in order.
Doesn’t use much memory as all the sorting is done using the original list.

Question 16

Describe the process of a merge sort

Answer 16

Process of a merge sort:

1) Split the list in half (these smaller lists are called sub-lists), the second sub-list should start at the middle item
2) Keep repeating step 1 until all of the sub-lists 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.
4) Repeat step 3 until you have merged all of the sub-lists together.

Question 17

Give an advantage of the merge sort

Answer 17

Advantages:
More efficient and quicker on large lists compared to the bubble sort
It has a consistent running time no matter how ordered or unordered the list is

Question 18

Give a disadvantage of the merge sort

Answer 18

Disadvantages:
It is slower than other sorts, for smaller lists
If the list is already sorted, it still has to go through the whole process
It uses more memory to complete the sort with the separate lists

Question 19

What is an insertion sort?

Answer 19

An insertion sort is an algorithm used to sort a dataset of values by means of a sorted and unsorted list.
Unsorted itemms are compared with the sorted list and placed in the correct position in the sorted list.

Question 20

Describe the process of an insertion sort

Answer 20

Process of an insertion sort:

1) Element 1 is highlighted as ‘sorted’
2) The rest of the elements are ‘unsorted’
3) Compare element 1 in the ‘unsorted’ list to each element in the ‘sorted’ list
4) If the unsorted element 1 is smaller, put it in front of the element it was compared with
5) Move the others along
6) Or, if unsorted element 1 is larger, compare it with the next value in the sorted list
7) Or, if there are no more elements in the sorted list, put unsorted element 1 in the final position

Question 21

Give an advantage of the insertion sort

Answer 21

Advantages:
It is the best sort when the list is already ordered
It is an intuitive way of sorting things and can be easily coded
It copes very well with small lists
All the sorting is done on the original list, so it doesn’t require much additional memory (like the bubble sort)
It is very quick to add items to an already ordered list
Twice as fast as a bubble sort

Question 22

Give a disadvantage of the insertion sort

Answer 22

Disadvantages:
It is the worst sort when the list is unordered
More complex to code than the bubble sort
Slower than a merge sort

Question 23

What is a merge sort?

Answer 23

A merge sort is an algorithm that splits a list apart by finding the midpoint and keeps splitting until there are sub arrays of 1 item. The values are then reordered and put back together.