Searching and Sorting Algorithms

Question 1

How does a binary search work?

Answer 1

1) Find the middle item in the ordered list
2) If this is the one your looking for then it stops.
3) If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half or vice versa.
4) You’ll be left with a list that is half of the original list. Keep repeating the first 3 steps until you find the item your looking for.

Question 2

What does a binary search do?

Answer 2

Look for items in an ordered list.

Question 3

What does a linear search do?

Answer 3

A linear search checks each item of the list in turn to see if it’s the correct one. It stops when it’s found the item or has checked every item.

Question 4

How does a linear search work?

Answer 4

1) Look at the first item in the unordered list.
2) If this is the item you’re looking for, then it stops as you found it.
3) If not, look at the next item in the list.
4) Repeat steps 2-3 until you find the item that you’re looking for or you’ve checked every item.

Question 5

What are the differences between a binary and linear search?

Answer 5

Linear is much simpler, but not as efficient. It can be used on an unordered list as well.

Question 6

Due to linear searches being insufficient what are they often used on?

Answer 6

Only small lists

Question 7

Why are binary searches more efficient than a linear one?

Answer 7

Takes fewer steps (once it has been ordered) to find the item which makes it more suitable for larger lists.

Question 8

What is a bubble sort?

Answer 8

Is used to sort an unordered list of items by comparing pairs of items. It is very simple to follow but cam often take a while to sort.

Question 9

How does a bubble sort work?

Answer 9

1) Look at the first two items in the list.
2) If they’re in the right order leave them otherwise swap them.
3) Move on to the next pair (3rd and 4rd entries) and repeat step 2.
4) Repeat step 3 until you get to the end of the list - this is called 1 pass. The last item will be in the correct place, so don’t include it in the next pass.
5) Repeat steps 1-4 until there are no swaps in a pass.

Question 10

What are the advantages of a bubble sort?

Answer 10

• it’s 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 (would only have to do 1 pass to know if the items are ordered)
• Doesn’t use very much memory as all the sorting is done using the original list.

Question 11

What are the disadvantages of a bubble sort?

Answer 11

• inefficient way to sort a list

- due to being insufficient it doesn’t cope with very large lists.

Question 12

What is a merge sort?

Answer 12

It splits a list apart and then puts it back together in the correct order.

Question 13

The merge sort is a divide and conquer algorithm and takes advantage of what two facts?

Answer 13

• small lists are easier to sort than large lists

- easier to merge two ordered lists than two unordered ones.

Question 14

How does the merge sort work?

Answer 14

1) split the list in half
2) Keep splitting the list until all the lists only contain 1 item.
3) Merge pairs of the lists so each list has twice has many items. Each time you merge them sort the items into the right order.
4) Repeat step 3 until all the lists are merged together into the original list in the correct order.

Question 15

What are the smaller lists called when you split them using a merge sort?

Answer 15

sub-lists

Question 16

What is a problem with merge sorts?

Answer 16

You’ll often be unable to split or merge lists evenly. For example sometimes you’ll have to merge a list containing two items with a list containing one item to make a list of 3 items.

Question 17

What are the advantages of merge sorts?

Answer 17

• in general it’s much more efficient and quicker than the bubble sort and insertion sort algorithms for large lists.
• it has a very consistent running time regardless of how ordered the items in the original list are.

Question 18

What are the disadvantages of merge sorts?

Answer 18

• it’s 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 in order to create the separate lists.

Question 19

Due to its efficiency the merge sort algorithms or variations of it are used in what?

Answer 19

Many programming languages like:
- Java
- Python
- Perl 
as the primary sorting algorithm.

Question 20

What is an insertion sort?

Answer 20

The simplest sorting algorithm and orders the items as it goes.

Question 21

How does the insertion sort work?

Answer 21

1) Look at the second item in the list.
2) Compare it to all the items before it in the list and insert it into the right place.
3) Repeat step 2 until all the items have been inserted into the correct order.

Question 22

What are the advantages of the insertion sort?

Answer 22

• an intuitive way of sorting things and can be easily coded.
• copes well with small lists, for this reason an insertion/merge hybrid sort is often used to take advantages of the strengths of each algorithm.
• all sorting is done on the original list so, like the bubble sort, it doesn’t require very much additional memory.
• very quick to add items to an already ordered list.
• also very quick at checking that a list is already sorted.

Question 23

What’s the insertions’ main disadvantage?

Answer 23

Doesn’t cope well with very large lists.