Simulación de Algoritmos de ordenación

Acerca de este experimento

Observa cómo bubble sort, insertion sort y merge sort transforman la misma entrada en orden ascendente. Haz una pausa en una comparación, avanza paso a paso por cada escritura o retrocede por todo el recorrido. Los recuentos separados de comparaciones de valores y escrituras en el array principal ayudan a distinguir el trabajo algorítmico de la duración de la animación.

Objetivos de aprendizaje

Seguir las comparaciones y escrituras de tres algoritmos de ordenación por comparación
Comparar el rendimiento con entradas desordenadas, ordenadas e invertidas
Distinguir el crecimiento cuadrático en el peor caso del crecimiento n log n

Cómo usarlo

1Mantén fija la entrada desordenada y la longitud del array. Completa bubble sort y anota sus comparaciones y escrituras.
2Reinicia con insertion sort y luego con merge sort, usando la misma entrada. Compara los recuentos finales.
3Prueba con una entrada ordenada y observa la salida anticipada de bubble sort y las pocas comparaciones de insertion sort.
4Usa «Anterior» y el control deslizante del seguimiento para examinar una fusión. Los búferes temporales pueden contener valores que ya no son visibles en sus posiciones originales del array principal.

El modelo

C_{bubble, worst} = \frac{n ( n - 1 )}{2}

Comparaciones de valores de bubble sort en el peor caso

T_{insertion, worst} = O (n^{2}), T_{merge, worst} = O (n lo g n)

Crecimiento del tiempo de ejecución de insertion sort y merge sort en el peor caso

W_{swap} = 2

Un intercambio se cuenta como dos escrituras en el array principal

Supuestos

Las entradas contienen enteros únicos del 1 al n. La mezcla usa una semilla fija para que todos los algoritmos reciban datos idénticos.
Una comparación es una prueba entre valores de datos, no una prueba de índice ni de límite de bucle. Una escritura es una asignación al array principal, incluida la clave de inserción aunque no cambie.
Las copias en búferes temporales de merge sort no se incluyen en el recuento de escrituras. El uso de memoria adicional no se incluye en los totales de operaciones mostrados.
La velocidad de reproducción se elige con fines didácticos y no es una prueba de rendimiento en tiempo real.

Pruébalo en clase

Q1¿Por qué bubble sort solo necesita n − 1 comparaciones con una entrada ya ordenada en esta implementación?
Q2¿Qué algoritmo realiza menos comparaciones con una entrada en orden inverso y la misma longitud de array?
Q3¿Por qué el número de fotogramas de la animación no es una medida fiable de la velocidad de un algoritmo?

Preguntas frecuentes

¿Por qué los valores parecen duplicarse brevemente durante la ordenación por inserción o por mezcla?

Un valor puede almacenarse temporalmente en una clave o en un búfer de mezcla mientras se sobrescribe el arreglo principal. La visualización muestra el contenido del arreglo principal en cada escritura; la unicidad se restablece cuando termina la operación.

¿La ordenación por mezcla siempre realiza menos escrituras?

No. La ordenación por mezcla tiene un crecimiento eficiente del número de comparaciones, pero escribe repetidamente los resultados mezclados en el arreglo. El recuento de operaciones depende de la entrada y de qué asignaciones se cuenten exactamente.