sort: to arrange something in an order
to use fast algorithms ex. binary search, array should be sorted
1. bubble sort
- not used very much (there are a lot of better algorithms)
- select first 2 items of an array and compare them
> if left is bigger than the right, swap them
> do the same with index 1, 2
> repeat ….
> when it reaches the end of an array, the first cycle of bubble sort ends
> do it all over again from the first item
- time complexity = O(N^2)
2. selection sort
- keep track of the location of the lowest item from the first item in a variable
> swap the lowest item with the first item
> next cycle starts from the second item
- time complexity = O(N^2)
- faster than bubble sort (less swaps occur)
ex. [5, 2, 6, 3, 1, 4]
int a = lowest item
a = 5 > a = 2 > a = 2 > a = 2 > a= 1 > a = 4
swap a with 5
start from second item (2)
3. insertion sort
- faster than selection sort (selection sort scans all the elements, insertion sort scans items that are needed)
- time complexity = O(N^2)
three sort algorithms are expressed the same in the Big O notation, but their speed may differ.
