El misterio de quicksort.
Hoy me pasaba algo rarísimo, en una practica de algoritmos de ordenación, al utilizar quicksort en su caso medio el coste era
n log n, en el peor (para un vector ordenado) cuadrático, pero con vectores MUY grandes, ambos costes convergían.
Garantizo que nada en el código estaba mal, y ha sido un profesor quien ha dado con el quid de la cuestión. Podría dejar la resolucióndel enigma al lector… pero no sé si hay datos suficientes para deducir que pasaba.
Estaba usando muy pocas claves distintas (27 para vectores de 100000 elementos). ¿Porque hacía eso que el caso peor y el medio tuviran un coste similar?
La explicación es sencilla; el Quicksort tradicional tiene 3 casos malos (orden cuadrático):
-un vector ordenado
-un vector inversamente ordenado
-un vector de elementos iguales (la comparacíon “<=” lo hace equivalente a un vector ordenado).
Teniendo pocas claves en un vector muy grande, se forman grandes grupos de claves idénticas.
Solución: Usar muchas claves diferentes (todo el rango de enteros en ADA).
Este es otro argumento a favor de los algoritmos de ordenación adaptativos, normalmente usar pocas claves será una gran ventaja. ¿Pero y con un texto?Muchas letras iguales seguidas no habrá… pero con 27 claves (la letras), seguro que hay grandes grupos ordenados en la mayor parte de los vectores. Además, un texto no es aleatorio.