Math
Carrera de ordenaciones
Tres ordenaciones recorren el mismo arreglo a la misma velocidad en COMPARACIONES, y termina primero quien preguntó menos. Lo decide el desorden, no el tamaño: sobre una entrada ordenada la inserción usa 63 comparaciones y el quicksort 2016.
Qué ocurre
Tres carriles, un arreglo y un presupuesto de trabajo común: las tres ordenaciones avanzan el mismo número de comparaciones - o de movimientos, si cambia la unidad -, así que termina primero la que necesitó menos de esa unidad, no la que se dibuja más rápido. Todos los carriles hablan el mismo idioma: las dos claves comparadas llevan contorno dorado, una clave recién escrita destella en verde, un pivote lleva una marca roja, el tramo en trabajo va entre corchetes, los elementos en su lugar definitivo reciben un pie verde, y la clave que sostiene la inserción flota sobre el hueco donde caerá. Prediga el ganador antes de «Salida», o avance la carrera unidad a unidad. Pruebe las entradas: en un arreglo ordenado la inserción termina casi en seguida mientras quicksort con el último elemento como pivote cae en su peor caso; el orden inverso es el peor caso de la inserción; con claves repetidas el color es la posición en la entrada, y la mezcla conserva el orden de claves iguales mientras quicksort las revuelve. Cada carril muestra también el tiempo real de la ejecución en este ordenador - una tercera magnitud, nunca la unidad de la carrera.
Ecuaciones del módulo
Ecuaciones n elementos, y la carrera se corre en COMPARACIONES - la cantidad de la que tratan las fórmulas la ordenación por inserción MUEVE un elemento exactamente tantas veces como inversiones tiene la lista: una identidad sobre TODA permutación, comprobada sobre las n! para n <= 8 comparaciones de inserción = inversiones + (n − 1) − (mínimos de prefijo en i >= 1); promedio = n(n−1)/4 + n − H_n EXACTAMENTE: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 ordenación rápida (Lomuto, último elemento como pivote) promedio = 2(n+1)H_n − 4n EXACTAMENTE: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 peor caso de la ordenación por mezcla = n·ceil(lg n) − 2^ceil(lg n) + 1 - una fórmula, no una cota: 321 con n = 64, frente a ceil(lg n!) = 296, el mínimo de CUALQUIER ordenación por comparación los dos coinciden para n <= 4 y se separan después; la ordenación por mezcla además escribe n·lg n elementos sea cual sea la entrada - 384 con n = 64 64 elementos, todos los lugares mezclados: 1001 inversiones; inserción 1057 comparaciones / 1001 movimientos, mezcla 307 / 384, ordenación rápida 352 / 306 64 elementos, entrada ya ordenada: inserción 63, mezcla 192, ordenación rápida 2016 - y 2016 es n(n−1)/2, el PEOR caso de la ordenación rápida la mezcla supera a la inserción con 15 lugares mezclados de 64 (269 frente a 246): el umbral es el desorden, no el tamaño - con una entrada aleatoria la mezcla va por delante desde n = 4 claves iguales, 64 elementos sobre 8 valores: pares que quedan en orden inverso - inserción 0, mezcla 0, ordenación rápida 77
