Bubble Sort:

• Sorts items in pairs, if one is larger it is swapped and move down one number
• The largest value 'bubbles' to the top
• Stops after 0 comparisons
•  Once the algorithm finishes there is usually a final pass to check the number is in order (gives 0 comparisons)
• Easy to program but is bad when the list is in reverse order
• Has a quadratic order - time complexity of  O(n^2) so can be inefficient for larger lists

Pseudo Code:

Start

    noSwapps = False

    WHILE noSwapps == False

        for i to length of list - 1

             if i  > i+1

                  swap

Stop

Insertion Sort:

• Splits' the list into two halves working from left to right
• Gets a new item from the list, finds it place in the sorted list and places it here
• Finds the correct place using swaps
• Starts with the first element as the sorted list of length one, then adds the next element to the right and finds its place in the list
• Finishes when all numbers have been added to the ordered list no final check needed
•  Good because it allows items to be added and sorted into an array at any time and is useful for smaller lists (Good with memory)
• Good when the list has almost been sorted
• Time complexity of O(n^2) so can be slow again on big lists

 

Quick Sort:

• Divide and conquer
• During the partition step it divides the array into 2 groups depending on the pivot (the split) which doesn't need to be the middle element
• The best pivot value is the middle however this takes time so a random value is chosen
• This will split so that all the numbers to the left of the pivot are less than the pivot and all the numbers to the right are greater than the pivot but not in order
• Work in from each end of the list to put the numbers on the correct side to swap numbers from each side
• Another partition step occurs halfway through the groups that were just made before - similar to a binary search
• Uses recursion to keep splitting the partitions until the partitions are of size 0 or 1
• Time complexity of O(n log2(n))
• Very fast compared to the 2 other sorts on larger lists but can be complicated to program