Bubble sort works by iterating through each item in the array, and testing if it is smaller or larger than the element next to it. If the right element is smaller, then the items are swapped,
thus the smaller items 'bubble' up to the left-hand side each iteration of the array. The algorithm keeps track of weather a swap was made or not, and stops once it iterates through the whole list
without making a swap, indicating the array is correctly sorted.
Bubble sort has a worst case and average case time complexity of O(n2), and a best case time complexity of O(n).
Example implementation in C++
Selection sort works by iterating through the unsorted list and 'selecting' the smallest value, and it places this value at the end of the sorted array.
Selection sort has a best case, average case, and worst case time complexity of O(n2).
Example implementation in C++
Insertion sort works by iterating through the unsorted list and 'inserting' each item into it's correct ordered position by swapping the the element with the element to it's left
if the left element is larger than the itself, and continues until the array is sorted.
Insertion sort has a worst case and average case time complexity of O(n2) and a best case time complexity of O(n).
Example implementation in C++
Merge sort works by diving the array into smaller and smaller sub-arrays, sorting the sub-arrays, and then merging back together. The algorithm recursively calls itself on the front and back half
of the array that is given until it reaches a base-case of 1 element (an array of 1 element is considered sorted), and then works back up. It merges the arrays by comparing the first element in each sorted sub-array and adding the
smaller one to the new sorted sub-array until one of the sorted sub-arrays are empty, at which point the rest of the elements in the other sorted sub-array are appended to the new sorted sub-array.
Merge sort has a worst case, average case, and best case time complexity of O(n*log(n)).
Example implementation in C++
Quick sort works by selecting a 'pivot' value, and then 'partitioning' the array. The partition process simply puts all the values in the unsorted array that are less than the 'pivot' value
on the left hand side of the array, and ignores the values greater. After the partition, the 'pivot' value can be placed immediately to the right of all the elements that are less than it. This guarantees that the
'pivot' value is now in its sorted position, because all the values to the left of it are less than it, and all the values to the right are greater than it.
Quick sort has a worst case time complexity of O(n2) and a best case and average case time complexity of O(n*log(n))
