Optimizando Quicksort.
Yo soy de la creencia de que tiene que haber un algoritmo de ordenación mejor que Quicksort, un algoritmo que haga el numero imprescindible de comparaciones y ni una más.
Pero mientras no se me ocurra otro algoritmo, lo mejor que hay es Quicksort :P.
Una practica común es añadirle pequeñas optimizaciones a Quicksort, como que al trabajar con pocos elementos se use inserción o que si se detecta un caso malo se cambie a otro algoritmo (heapsort en el caso de introsort).
Otra posibilidad sería recorrer primero el vector de elementos, para comprobar si esta o no ordenado (en orden directo o inverso). De esta forma si no lo esta tendremos ya un “buen” pivote (el primer elemento no ordenado).
Esto añadirá posiblemente muchas comparaciones (máximo O(n)), así que no se si será practico, aunque el mejor caso sería O(n) (para vectores ordenados).
¿Y un algoritmo de ordenación que busque trozos ordenados (de forma directa o inversa) en el vector y luego los junte (a la mergesort)? Su peor caso sería n/2 vectores ordenados, de 2 elementos, a juntar. El mejor n-1 comparaciones para vectores ordenados.
Aprovechare la última practica de metodología de la programación para probar la eficiencia de versiones de todos estos algoritmos.