Carrera de algoritmos de ordenamiento

El ordenamiento de burbuja hace exactamente n(n−1)/2 comparaciones en el peor caso — unas 2000 para n=64. Cada pasada debe recorrer toda la región restante sin ordenar, sin salida anticipada. La partición de quicksort coloca el pivote en su posición final y divide el problema en dos subproblemas; cada nivel de recursión realiza O(n) trabajo a lo largo de O(log n) niveles, dando O(n log n) en total. La trampa: si el pivote siempre cae en un extremo — por ejemplo, entrada ordenada con el último elemento como pivote — la partición degenera en n subproblemas de tamaño n−1, n−2, ... que suman O(n²). El pivote del elemento central usado aquí evita eso, por lo que la entrada invertida se mantiene rápida. Los valores con pocos únicos son el caso interesante: cuando muchos elementos igualan al pivote, intercambiar valores idénticos desperdicia trabajo y puede acercarse a lo cuadrático. El Big-O te indica la clase de crecimiento; las constantes, la sensibilidad a la entrada y el comportamiento de la caché determinan qué algoritmo realmente conviene usar.

Esta carrera puntúa cada algoritmo contando comparaciones e intercambios, no con un cronómetro. El tiempo real depende de tu CPU, del navegador y de qué más se esté ejecutando, así que el mismo código puede parecer rápido o lento en distintas máquinas. Contar operaciones da una medida limpia y reproducible del trabajo realmente hecho: la misma entrada siempre produce los mismos recuentos, lo que te permite comparar los algoritmos en sí y no el hardware.

Tony Hoare inventó Quicksort en 1959, siendo estudiante visitante en Moscú, mientras trabajaba en un proyecto de traducción automática. Para buscar una frase rusa en el diccionario, primero necesitaba ordenar sus palabras alfabéticamente, y el método habitual era desesperadamente lento. Su solución, particionar en torno a un pivote, se convirtió en uno de los algoritmos más usados de la historia. Las barras que compiten aquí provienen de un problema lingüístico, no informático.