Ordenamientos elementales
Burbuja, selección, inserción: todos O(n²).
Inserción es el que importa.
Tres ideas
- Burbuja — intercambia pares adyacentes; el mayor burbujea hasta el final
- Selección — busca el mínimo en cada pasada; solo n intercambios
- Inserción — hace crecer un prefijo ordenado, deslizando cada elemento hacia atrás
- Todos in-place, O(1) de espacio extra
Mira el ordenamiento por inserción
El prefijo azul crece; el elemento naranja se desliza a su lugar.
Datos casi ordenados → casi nada de movimiento.
O(n²) vs O(n log n)
En n=2000, inserción es 500× más lento que Timsort, y la brecha solo crece.
El ordenamiento por inserción es adaptativo
- 8000 elementos aleatorios: ~710 ms
- 8000 casi ordenados: ~38 ms → 19× más rápido
- Por eso Timsort lo usa en los runs chicos
Para llevar
Inserción para lo chico o casi ordenado; O(n log n) para el resto.
Aprende a leer un ciclo anidado como una cuadrática. Sigue: merge sort.