Ordenamiento comparativo
Mapa conceptual
Qué es ordenar por comparación
Son algoritmos que solo deciden el orden preguntando «¿es a menor que b?». No explotan el rango de los valores (eso lo hacen counting sort o radix). Su costo se mide en comparaciones e intercambios.
La familia cuadrática
- Burbuja: intercambia vecinos desordenados hasta que nada burbujee; simple y lento, O(n²).
- Inserción: toma cada elemento y lo coloca en la parte ya ordenada; O(n²) pero muy bueno con datos casi ordenados o pequeños.
- Selección: busca el mínimo y lo pone al frente, n veces; siempre O(n²), pocas escrituras.
La familia n log n
- Merge sort: divide en mitades, ordena y fusiona; O(n log n) garantizado y estable, pero usa memoria extra O(n).
- Heap sort: monta un heap y extrae extremos; O(n log n) garantizado e in situ, no estable.
- Quick sort: elige un pivote y particiona; promedio O(n log n), rápido en la práctica, pero con peor caso O(n²) si los pivotes son malos.
[Crecimiento: n log n contra n cuadrado]
Esta actividad interactiva ('Grafico interactivo') requiere el motor completo de Lumbre. El contenido estatico se muestra arriba; para la experiencia interactiva, visita la version online de este objeto.
| Algoritmo | Mejor | Promedio | Peor | Estable | Memoria extra |
|---|---|---|---|---|---|
| Insercion | O(n) | O(n2) | O(n2) | Si | O(1) |
| Merge | O(n log n) | O(n log n) | O(n log n) | Si | O(n) |
| Heap | O(n log n) | O(n log n) | O(n log n) | No | O(1) |
| Quick | O(n log n) | O(n log n) | O(n2) | No | O(log n) |
¿Cuál es el peor caso de quicksort y de qué depende?
¿Por qué n log n es el suelo?
Ordenar n elementos equivale a distinguir entre n! permutaciones posibles. Cada comparación binaria divide el espacio de posibilidades entre dos, así que hacen falta al menos log₂(n!) comparaciones, que por Stirling es Θ(n log n). Ningún algoritmo comparativo puede bajar de ahí.
Estabilidad
Un ordenamiento es estable si conserva el orden relativo de elementos empatados. Importa cuando se ordena por varias claves sucesivas: merge e inserción son estables; heap y quick no.
Merge sort es estable y garantiza O(n log n) en el peor caso.
Elegir en la práctica
- Datos pequeños o casi ordenados: inserción.
- Se requiere estabilidad o garantía de peor caso: merge sort.
- Memoria limitada: heap sort.
- Velocidad promedio y buen uso de caché: quick sort (o introsort, que combina con heap ante mal pivote).
Errores frecuentes
- Cotizar quicksort solo por su promedio: su peor caso O(n²) es real si el pivote es adverso.
- Ignorar la estabilidad al ordenar por claves múltiples.
- Asumir que O(n log n) «es igual» entre algoritmos: constantes, memoria y locality importan.
Clasifica cada algoritmo por su peor caso:
O(n2)
O(n log n)
USFCA — visualizaciones
Animaciones comparativas de todos estos algoritmos.
Tienes que ordenar un millón de transacciones ya casi ordenadas, conservando el orden de registro en empates. ¿Qué algoritmo eliges y por qué? Argumenta con costo, estabilidad y memoria.
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.