Paper 2 - Sorting Algorithms

How do you perform a bubble sort

1. Look at the first two items in the list

2. If they’re in the right order, don’t do anything. If they’re in the wrong order, swap them

3. Move on to the next pair of items and repeat step 2

4. Repeat step 3 until you get to the end of the list

5. Repeat steps 1-4 until there are no swaps in a pass

what are the advantages of bubble sort

Its a simple algorithm than can be easily implemented on a computer

Its an efficient wat to check if a list is already in order

Doesn’t use very much memory as all the sorting is done using the original list

what are the disadvantages of bubble sort

its an inefficient way to sort a list

does not cope well with very large lists of items

How do you perform a merge sort

1. split the list in half

2. keep repeating step 2 until all lists only contain one item

3. merge pairs of sub lists so that each sub lists has twice as many items. Each time you merge the sub-lists, sort the items into the right order

   1. repeat step 3 until all sub-lists are merged together

what are the benefits of merge sort

more efficient and quicker than bubble sort and insertion sort for large lists

has a very consistent running time regardless of how ordered the items in the original list are

what are the disadvantages of Merge sort

its slower than other algorithms for small lists

even if the lists 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

how do you perform an insertion sort

1. look at the second item in the list

2. compare it to all items before it and insert the number into the right place

   1. repeat steps 2 for all the items in the list so they are all sorted

what are the advantages of insertion sort

can be easily coded

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 sorted list

very quick at checking a list that is already sorted

what is the main disadvantage of insertion sort

doesnt cope very well with very large lists