2.1.3 - Searching and sorting algorithms

Name two standard teaching algorithms.

• Binary search

• Linear search

Describe binary search.

1. Find the median in an ordered lost

2. If this the item then stop

3. If not, compare the item to the median

4. If it comes before, remove the second half of the list (more the end to the item before the median)

5. If it comes after, remove the first half of the list (move the start to the item after the median)

6. Repeat steps until you find the item

Describe linear search.

1. Look at the first item in an unordered list

2. If this is the item, stop

3. If not, look at the next item

4. Repeat until you find the item or you’ve checked every item

Compare linear and binary search.

• Linear search is much simple than binary search

• Linear search is not as efficient as binary search

• Linear search can be used on any type of list - it does not have to be ordered

• In general, a binary search takes fewer steps to find the item than linear search - this makes binary search more suitable for large lists

Name the three standard sorting algorithms.

• Bubble sort

• Merge sort

• Insertion sort

Describe bubble sort.

• look at the first two items in the list

• If they’re in the wrong order - swap them

• Move onto the next pair of items repeat step 3 - until you get to the end of the list (called one pass)

• Repeat these steps until there are no swaps in a pass

What is merge sort an example of?

Example of a divide-and-conquer algorithm

Describe merge sort.

• split the list in half (smaller lists are called sub-lists)

• Keep repeating this on the sub-list until each list only contains one item

• Merge pairs of sub-lists so that each sub-list has twice as many items -sorting the items into the right order as you do this

• Repeat this until you’ve merged all the subsist together

Describe insertion sort.

• look at the second item in a list

• Compare it to all the items before it

• Then insert the number into the right place

• Repeat this until the last number in the list has been inserted into the correct place

What are the advantages of bubble sort?

• simple algorithm that can be implemented on a computer

• Effective way to check if a list is already in order - you would only have 1 pass of n-1 comparisons

• Doesn’t use much (additional) memory as all the sorting is done using the original list

What are the disadvantages of bubble sort?

• inefficient way to sort a list

• Worst case scenario would be n(n-1) / 2 comparisons

• Due to being inefficient, it dies not cope well with very large lists of items

List the advantages of merge sort.

• generally, it is more efficient and quicker than the bubble sort and the insertion sort for large lists

• Has a very consistent running time, regardless of how ordered the items in the original list are

List the disadvantages of merge sort.

• slower than other algorithms for small lists

• Goes through the entire process, even if the list is already sorted

• Uses more memory than the other sorting algorithms in order to create the separate lists

List the advantages of insertion sort.

• easily coded and implemented onto a computer

• Copes very well with small lists

• All sorting is done on the original list - so it doesn’t require very much additional memory

• Very quick to add items to an already ordered list

List the disadvantages of insertion sort.

• doesn’t cope with very large lists

• Same as bubble sort - n(n-1) / 2