Week 9 of Coding

There are many ways to sort a piece of data according to its complexity and desired organization. I'm not talking about the sort method that is build in python. There are in fact complex algorithms coded just for sorting.

```````````````
Bubble Sort

numbers with index: 0 - 1- 2- 3- 4 - 5

1.compare every pair of numbers in turn ( 0 and 1, 1 and 2)
2. switch around if bigger one in the front
3. the biggest number would end up at the back after a number of switches.
4. redo the comparison from the beginning.

this takes huge amount of time, because it requires going over n comparisons for n numbers in the list and then n rounds in total.

```````````````
Selection Sort

this is better than Bubble sort in that it only makes one 'comparison' each round.

1. find the biggest number of the list.
2. place at the back
3. repeat

```````````````
Insertion Sort

Troublesome as well, but works in a new way from the two above.

numbers with index: 0 - 1- 2- 3- 4 - 5

1. assume number at index 0 is sorted
2. compare index 1 to 0, switch if smaller one at the back
3. assume index 0 and 1 are sorted sub-list
4. compare index 2 to each number in sub-list and make switches.
5. now index 0, 1, and 2 are the sorted sub-list
6. repeat

This is like bubble sort, it make n comparison at most for the n numbers in list, and then repeat for n rounds.

```````````````
Merge Sort

I always thought that this is a hard concept. Because it is much different from any other sorting method.

1. split the list in half
2. split each sub-list in half (until you cannot split anymore)
3. sort the numbers in each sub-list
4. merge with the other sub-list when splitting on the upper level before. Sort it
5. continue to merge all sub-lists