Sorting Race — apuesta por el algoritmo más rápido
Dos algoritmos de ordenación compiten sobre el mismo array. Apuesta por el ganador: la mejor complejidad pierde más de lo que crees. Gratis.
Seis carreras. Mismo array, dos algoritmos: elige el que creas que acabará primero.
Cómo jugar
- Dos ordenaciones, un array. Apuesta por la que creas que acabará antes y mira.
- Gana la que use menos operaciones — comparaciones más movimientos —, no la de mejor complejidad teórica.
- Lee el tamaño y la forma. Por debajo de unas veinte barras ganan las simples; en un array casi ordenado la inserción gana a todo.
- Un acierto paga 50 y un fallo cuesta 50. Seis carreras, y empiezas con 100.
Cómo funciona
Dos algoritmos de ordenación compiten sobre el mismo array, dibujado como barras, y tú apuestas por cuál termina primero. Cada ronda enfrenta a un algoritmo O(n log n) contra uno O(n²), así que siempre hay un favorito obvio, y el favorito obvio se equivoca casi la mitad de las veces. Lo que decide de verdad es el tamaño del array y su forma: la ordenación por inserción termina un array casi ordenado con la veinteava parte de las operaciones que necesita un quicksort ingenuo, y por debajo de unos veinte elementos las constantes pesan más que la complejidad asintótica, que es justo por lo que las bibliotecas reales cambian a inserción por debajo de ese umbral. El ganador se decide por número de operaciones, no por un cronómetro, así que el resultado es el mismo en cualquier máquina. Se ejecuta en tu dispositivo, no se envía nada y no hace falta registrarse.
Operaciones significa comparaciones más movimientos de datos, contando un intercambio como uno, sobre implementaciones de manual. Las ordenaciones reales de biblioteca son híbridas y ganarían casi todas las carreras, que es precisamente lo que se quiere ilustrar.
Preguntas frecuentes
¿El mejor algoritmo no es siempre el más rápido?
A estos tamaños, no. La notación O describe cómo crece el coste, no cuánto vale, y oculta por completo la constante. Medido sobre 400 partidas: apostar por la mejor complejidad teórica acierta 3,19 de 6, frente a 3,00 apostando siempre al mismo lado. Dos reglas — un array casi ordenado y un array pequeño favorecen ambos a la ordenación simple — aciertan unas 4,8 de 6.
¿Cómo se decide el ganador?
Contando comparaciones y movimientos, calculados antes de dibujar nada. La animación reproduce esa cuenta al mismo ritmo en ambos lados, así que el que necesita menos operaciones termina antes en pantalla por la misma razón por la que gana. Un visualizador que hiciera correr dos bucles en tiempo real daría una respuesta distinta en una máquina rápida que en una lenta.
¿Por qué a veces quicksort va tan mal?
Usa el último elemento como pivote, la versión ingenua. En un array ya ordenado o casi ordenado ese pivote es la peor elección posible y las particiones degeneran, así que hace trabajo cuadrático justo con la entrada que la ordenación por inserción resuelve más rápido. Las implementaciones reales eligen mediana de tres o pivote aleatorio precisamente para evitarlo.
¿Qué significan las formas del array?
Aleatorio es barajado. Casi ordenado está en orden salvo unos pocos intercambios adyacentes. Invertido está exactamente al revés. Pocos valores tiene solo cuatro valores distintos, que es donde la partición de un quicksort ingenuo se desmorona. Diente de sierra repite la misma rampa varias veces.