Partial Selection Sort

O que difere esse do original é que o laço externo é limitado a rodar k vezes. Complexidade:

$$\begin{eqnarray*} T\left( n\right) & = & \sum _{i=0}^{k-1}n-i\\ & = & k\frac{n... ... & = & \frac{2nk-k^{2}-k}{2}\\ & = & O\left( nk+k^{2}\right) \end{eqnarray*}$$

Pela fórmula analítica fica fácil de ver pq o selection decresce tanto em relação ao insertion: apeser de ser inicialmente menor do que o insertions, k tem um grande peso nesse algoritmo.