Selection Sort

Good for small arrays.
\(f(n)=\sum_{i=1}^{n-1}(n-i)=(n-1)+(n-2)+\dots+2+1=\frac{n(n-1)}{2}\)
Time Complexity:\(O(n^2)\)

Input: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Output: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
\(n=10\)
counter: \(106\) (why not \(45\)

Worst case for selection sort(secends).

The 106 means number of executions.
The 45 means number of checking.(whether the v[i] is less than the v[j] in code.)

Code:(cpp)

Red: int max(the graph number is inverted)
Blue: int j
Yellow: Sorted (first iteration)(int i)

(why blue start from 8? Isn't it 5?
\(n+(n-1)+\dots+3+2=\frac{(n+2)(n-1)}{2}\) why?