Cargando aplicación...
Preparando tu experiencia meskeIA
Aprende cómo funcionan los algoritmos de ordenación paso a paso con visualizaciones interactivas
procedimiento bubbleSort(A) para i desde 0 hasta n-2 para j desde 0 hasta n-i-2 si A[j] > A[j+1] entonces intercambiar(A[j], A[j+1]) fin si fin para fin parafin procedimientoCompara elementos adyacentes e intercambia si están desordenados. Simple pero ineficiente para arrays grandes.
Comprende las diferencias, cuándo usar cada algoritmo y cómo elegir el más adecuado para tu proyecto
| Algoritmo | Mejor Caso | Caso Promedio | Peor Caso | Espacio | Estable | Ideal para |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Aprender, arrays muy pequeños |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimizar escrituras en memoria |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Arrays casi ordenados, pequeños |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Uso general, datos aleatorios |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí | Ordenación garantizada, objetos |
La notación O grande describe cómo crece el tiempo de ejecución con el tamaño de la entrada. O(n²) significa que si duplicas el tamaño del array, el tiempo se cuadruplica. O(n log n) crece mucho más lento: un array de 1.000 elementos tarda ~10.000 operaciones en vez de ~1.000.000 con O(n²).
Un algoritmo estable mantiene el orden relativo de elementos con claves iguales. Por ejemplo, si ordenas estudiantes por nota y dos tienen la misma nota, un algoritmo estable los mantiene en el orden original. Estables: Bubble, Insertion, Merge Sort. Inestables: Selection Sort, Quick Sort (implementación estándar).
Los algoritmos in-place (Bubble, Selection, Insertion, Quick) ordenan usando solo O(1) o O(log n) de memoria extra. Merge Sort necesita O(n) de memoria adicional para el array temporal durante la fusión, lo que puede ser un problema con arrays de cientos de millones de elementos.
| Algoritmo | Mejor caso | Caso medio | Peor caso | Espacio | Estable | Cuándo usarlo |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Solo para enseñar conceptos o detectar arrays ya ordenados |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Cuando minimizar escrituras en memoria es crítico (EEPROM) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sí | Arrays pequeños (<50) o casi ordenados |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí | Cuando necesitas garantías de peor caso o estabilidad |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Uso general en memoria, datos aleatorios con pivote aleatorio |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Cuando necesitas O(1) espacio extra con peor caso garantizado |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Sí | Enteros en rango pequeño y conocido (k << n) |
“FAANG pregunta 'ordena este array en O(n log n)'. Merge Sort garantiza el peor caso. Quick Sort es más rápido en la práctica pero tiene peor caso O(n²).”
Tip: Mergesort para garantías, Quicksort para rendimiento medio.
“Ordenar 10.000 entidades por distancia al jugador cada frame (60fps). Insertion sort para arrays casi ordenados (movimiento incremental) es 10x más rápido que Quicksort.”
Tip: Analiza si los datos están casi ordenados antes de elegir algoritmo.
“PostgreSQL usa introsort (híbrido QuickSort + HeapSort + InsertionSort) para ORDER BY. Cambia a algoritmo estable cuando necesita preservar orden relativo.”
Tip: Las BDs usan algoritmos híbridos adaptativos, no puros.
“Ordenar 10⁹ mediciones de sensor en disco (externo): Merge Sort externo en bloques de 64MB, 1,2TB procesados en 4 horas.”
Tip: Para datos que no caben en RAM, solo Merge Sort externo es viable.
La constante importa: Quicksort tiene mejor localidad de caché (acceso secuencial), menos operaciones de copia y overhead de recursión. En la práctica es 2-3x más rápido que Mergesort para datos en memoria.
Casi nunca en producción. Solo es útil para enseñar conceptos o detectar si un array ya está ordenado (termina en O(n) con la variante optimizada). Con n>100 elementos, cualquier otro algoritmo lo supera.
Que elementos con igual clave mantienen su orden relativo original. Crucial cuando ordenas por múltiples criterios: primero por apellido, luego por nombre. Mergesort y Insertion Sort son estables; Quicksort y Heapsort no.
El algoritmo usado por Python y Java (Arrays.sort). Híbrido de Mergesort + InsertionSort que detecta subsecuencias ya ordenadas (runs) y las combina. Rendimiento real O(n) en datos casi ordenados, O(n log n) en peor caso.
Ocurre cuando el pivote elegido siempre es el mínimo o máximo: array ya ordenado con pivote en posición 0. Solución: elegir pivote aleatoriamente o usar ‘mediana de tres’.
Cuando los datos no caben en RAM. Se divide en bloques que sí caben, se ordena cada bloque, se guardan en disco y se fusionan (Merge Sort externo). Usado en bases de datos, Hadoop MapReduce.
Cuando el rango de valores es pequeño y conocido. Crea un array de contadores. Ordena n=1.000.000 enteros de 0-255 en O(n+k) ≈ O(n). Imposible para números flotantes o strings arbitrarios.
Ω(n log n) — demostrado por el argumento del árbol de decisión. Ningún algoritmo basado en comparaciones puede ser más rápido en el caso general. Radix Sort y Counting Sort lo superan porque no comparan.
No → Merge Sort externo. Sí → continúa.
n<50 → Insertion Sort (constante pequeña). n>50 → continúa.
Sí → Insertion Sort o Timsort. No → continúa.
Sí → Counting Sort o Radix Sort (O(n)). No → continúa.
Sí → Mergesort. No → continúa.
Sí → Heapsort. No → Quicksort con pivote aleatorio.
Python sort(), Java Arrays.sort(), C++ std::sort() — son híbridos optimizados que superan cualquier implementación manual.
Python sort()/sorted(), Java Arrays.sort(), C++ std::sort() son Timsort/Introsort optimizados. Más rápidos que cualquier implementación propia.
Para n<10.000 la diferencia entre O(n²) y O(n log n) es <1ms. Optimiza solo cuando el profiler lo confirma.
¿Ya casi ordenados? ¿Rango pequeño? ¿Muchos duplicados? La respuesta cambia el algoritmo óptimo.
Nunca uses siempre el primer elemento como pivote. Mediana de tres o pivote aleatorio evita el caso O(n²).
En arrays grandes, algoritmos con acceso secuencial (Mergesort, Heapsort) aprovechan mejor la caché L1/L2 que los de acceso aleatorio.
Si ordenas objetos por un campo, extrae el campo a un array auxiliar, ordena índices y reordena — evita mover objetos grandes.