Algoritmos en acción
Algoritmos en acción es una simulación interactiva gratuita de StudyFi Lab. Funciona directamente en el navegador, sin registro y sin instalar nada.
Ordenar y buscar, paso a paso
Experimentos
Ordenamiento de burbuja
El ordenamiento de burbuja compara elementos vecinos y los intercambia si están en el orden equivocado. Tras cada pasada, el elemento mayor ha «subido como una burbuja» hasta el final, así que la parte sin ordenar se acorta. Si una pasada no hace ningún intercambio, el arreglo ya está ordenado. En el peor caso necesita n(n−1)/2 comparaciones, es decir, O(n²).
Prueba esto: Elige la entrada invertida y compara las comparaciones con n(n−1)/2. Luego prueba un arreglo casi ordenado: termina tras unas pocas pasadas.
Ordenamiento por inserción
La ordenación por inserción funciona como ordenar cartas en la mano: la parte izquierda ya está ordenada y cada nuevo elemento (key) se desplaza a la izquierda hasta encontrar uno menor. Por el camino, los elementos mayores se mueven un lugar a la derecha. Con datos aleatorios es O(n²), pero con datos casi ordenados es casi O(n): un arreglo ordenado necesita solo n−1 comparaciones.
Prueba esto: Ejecútalo con un arreglo casi ordenado y luego con uno invertido. ¿Cuántas veces más desplazamientos necesita el invertido?
Ordenamiento por mezcla
El ordenamiento por mezcla divide el arreglo en dos mitades, ordena cada una de la misma forma (recursión) y luego mezcla las dos mitades ordenadas: siempre toma el menor de los dos elementos del frente. Dividir a la mitad da log₂ n niveles y cada nivel procesa los n elementos, así que el tiempo es O(n log n) en todos los casos. En caso de empate toma el de la izquierda, por eso es estable.
Prueba esto: Prueba un arreglo invertido y luego uno casi ordenado del mismo tamaño. Las comparaciones apenas cambian: el orden de entrada casi no importa.
Ordenamiento rápido
El ordenamiento rápido elige un pivote —aquí el último elemento del tramo (partición de Lomuto)— y reorganiza el tramo para que los menores queden a la izquierda y el resto a la derecha. Así el pivote queda en su lugar definitivo y las dos partes se ordenan igual. En promedio es O(n log n), pero si el pivote divide mal (por ejemplo, con un arreglo ya ordenado o invertido) cae a O(n²).
Prueba esto: Compara una entrada aleatoria con una invertida. En el arreglo invertido el pivote siempre es el mayor o el menor: observa cómo se disparan las comparaciones.
Búsqueda lineal vs. binaria
La búsqueda lineal revisa los elementos uno a uno, así que en el peor caso necesita n pasos: O(n). La búsqueda binaria solo funciona en un arreglo ordenado: mira el centro y, según el resultado, descarta una mitad entera. Tras cada paso queda como mucho la mitad, por eso bastan como máximo ⌈log₂(n+1)⌉ pasos: O(log n). Con 40 elementos son 6 pasos en vez de 40.
Prueba esto: Pon 40 elementos y busca el último valor. Luego elige un número que no esté en el arreglo: ¿cuántos pasos necesita cada búsqueda para saberlo?
Carrera de ordenamientos
Los cuatro algoritmos ordenan la misma entrada y, en cada carril, un paso es una comparación o un movimiento. Los algoritmos O(n²) (burbuja e inserción) crecen con el tamaño del arreglo mucho más rápido que los O(n log n) (mezcla y rápido). El orden también depende de la entrada: con un arreglo casi ordenado suele ganar la inserción.
Prueba esto: Lanza la carrera con un arreglo aleatorio de 40 elementos y luego cambia a casi ordenado. ¿Cambia el ganador?
Preguntas frecuentes
¿Qué es Algoritmos en acción?
Algoritmos en acción es una simulación interactiva gratuita de StudyFi Lab. Funciona directamente en el navegador, sin registro y sin instalar nada. Ordenar y buscar, paso a paso
¿Algoritmos en acción es gratis?
Sí. Algoritmos en acción es completamente gratis. Funciona en el navegador del ordenador, la tableta o el móvil, y no necesitas cuenta.
¿Qué puedo explorar en Algoritmos en acción?
Ordenamiento de burbuja, Ordenamiento por inserción, Ordenamiento por mezcla, Ordenamiento rápido, Búsqueda lineal vs. binaria, Carrera de ordenamientos.
¿Qué muestra el experimento «Ordenamiento de burbuja»?
El ordenamiento de burbuja compara elementos vecinos y los intercambia si están en el orden equivocado. Tras cada pasada, el elemento mayor ha «subido como una burbuja» hasta el final, así que la parte sin ordenar se acorta. Si una pasada no hace ningún intercambio, el arreglo ya está ordenado. En el peor caso necesita n(n−1)/2 comparaciones, es decir, O(n²).
¿Qué muestra el experimento «Ordenamiento por inserción»?
La ordenación por inserción funciona como ordenar cartas en la mano: la parte izquierda ya está ordenada y cada nuevo elemento (key) se desplaza a la izquierda hasta encontrar uno menor. Por el camino, los elementos mayores se mueven un lugar a la derecha. Con datos aleatorios es O(n²), pero con datos casi ordenados es casi O(n): un arreglo ordenado necesita solo n−1 comparaciones.
¿Estudias para un examen?
Sube tus apuntes y StudyFi los convierte en tarjetas, tests y pódcasts.