Selection sort

Consiste en buscar el minimo y ponerlo primero. Luego, buscamos el minimo de lo que nos queda de la lista, es decir, todo salvo la primera posicion. Ese minimo seria el segundo elemento, y lo ponemos donde va, "arrastrando" todo lo demas una posicion. Repetimos este proceso, hasta llegar al final de la lista.

La verdad que no tiene mucha mas profundidad que esa. Dado que buscar el minimo en una lista tiene costo $O (n)$ , y que estamos buscando el minimo de una lista cada vez mas pequeña, el costo en tiempo de este algoritmo lo podemos escribir como:

\sum_{i = 0}^{n - 2} (n - i - 1) = \sum_{i = 0}^{n - 1} i = \frac{n (n - 1)}{2}

Si hacemos la cuenta, podemos ver que terminamos teniendo una complejidad de $O (n^{2})$ , es decir, de orden cuadratico.