these sorts have O(n^2)

easy-to-implement

not-the-fastest

bubble sort

see implementation here

move through the list pair-wise, swapping pairs in wrong order

repeat this process until list is sorted

after each ‘run-through’ through the list, we are guaranteed that the highest element is at the end of the list

worst case: O(n^2)

average case: O(n^2)

best case: O(n)

adaptive: YES

stable: YES

selection sort

find the smallest element, swap it with first array slot

find the second smallest element, swap it with second array slot

repeat, until traversed through entire array