Algorithm - Sort

Compute Complexity

Simple Sort

Bubble Sort

- Simple sorting

1. Starts from the end to the begin, compare two values and switch them to put smaller one left.

2. When it reaches the begin. Mark the beginning as done. And do it again till all marks done.

Complexity

- Average: O(n^2)

- Worst: O(n^2)

- Best: 2n

ex) [ 5 3 2 9]

1. [ 5 3 2 9 ]
2. [ 5 2 3 9 ]
3. [ 2 5 3 9 ]
4. [ 2 5 3 9 ]
5. [ 2 3 5 9 ]
6. [ 2 3 5 9 ]
7. [ 2 3 5 9 ]
8. [ 2 3 5 9 ]

Python Code

Selection Sort

Insertion Sort

Efficient Sort

Heap Sort

Bubble Sort Varients

Distribution Sort

Refer: https://en.wikipedia.org/wiki/Sorting_algorithm#Simple_sorts