Complejidad de los algoritmos de ordenación
| Algoritmo | Mejor | Medio | Peor | Memoria | Estable |
|---|---|---|---|---|---|
| Burbuja | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Selección | O(n²) | O(n²) | O(n²) | O(1) | No |
| Inserción | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
La notación O indica cómo crece el número de operaciones con el tamaño n en el caso límite. Con n = 1000, n² es un millón y n·log₂n unas 10 000: por eso los algoritmos cuadráticos solo compensan con vectores pequeños.
Qué observar en la animación
- Burbuja e inserción con datos casi ordenados terminan enseguida: su mejor caso es lineal.
- Selección hace siempre las mismas comparaciones, n(n−1)/2, sin importar los datos, pero como mucho n − 1 intercambios.
- Quicksort con el pivote en el último elemento se vuelve cuadrático con datos ya ordenados o invertidos. Las implementaciones reales lo evitan con un pivote aleatorio o la mediana de tres.
- Mergesort hace casi las mismas comparaciones con cualquier entrada.
- Heapsort primero desordena aparentemente el vector al construir el montículo y luego va fijando los mayores al final.
Pulsa «Contar comparaciones de todos» para ver estas diferencias en números con el tamaño que hayas elegido.
Qué significa que un algoritmo sea estable
Un algoritmo es estable si dos elementos con la misma clave conservan su orden relativo. Importa cuando ordenas por varios criterios: si ordenas una lista de alumnos por nombre y después, con un algoritmo estable, por nota, los que tienen la misma nota siguen en orden alfabético.
Preguntas frecuentes
¿Qué algoritmo usan los lenguajes de programación?
Ninguno de estos tal cual. Python y Java (para objetos) usan Timsort, un híbrido estable de mergesort e inserción. C++ usa introsort, que empieza con quicksort y cambia a heapsort si la recursión se hace demasiado profunda, y usa inserción para tramos pequeños.
¿Se puede ordenar más rápido que n log n?
No comparando elementos: está demostrado que cualquier ordenación por comparaciones necesita Ω(n log n) en el peor caso. Algoritmos como counting sort o radix sort lo consiguen porque no comparan, sino que aprovechan que las claves son enteros acotados.
¿Por qué se cuentan comparaciones y escrituras?
Son las operaciones que dominan el coste. Contarlas permite comparar algoritmos sin depender de la velocidad del ordenador. Aquí un intercambio cuenta como dos escrituras.
Más herramientas de informática
Calculadora de subredes IPv4
Red, broadcast, hosts, wildcard y reparto VLSM con el AND en binario.
AbrirConversor de bases numéricas
Binario, octal, decimal, hexadecimal y bases 2–36 con divisiones sucesivas.
AbrirCalculadora de complemento a 2
Enteros con signo en Ca2, Ca1 y signo-magnitud, y sumas con desbordamiento.
AbrirConversor IEEE 754
Coma flotante de 32 y 64 bits con exponente sesgado y error de redondeo.
AbrirGenerador de tablas de verdad
Tabla de verdad de cualquier expresión, con minterms y formas canónicas.
AbrirMapas de Karnaugh
Expresión mínima en SOP y POS con los grupos marcados en el mapa.
Abrir