PUERTA | GATE-CS-2015 (prueba simulada) | Pregunta 9

¿Cuál de los siguientes cambios en QuickSort típico mejora su rendimiento en promedio y generalmente se realiza en la práctica?

1) Randomly picking up to make worst case less 
   likely to occur.
2) Calling insertion sort for small sized arrays 
   to reduce recursive calls.
3) QuickSort is tail recursive, so tail call 
   optimizations can be done.
4) A linear time median searching algorithm is used 
   to pick the median, so that the worst case time 
   reduces to O(nLogn)

(A) 1 y 2
(B) 2, 3 y 4
(C) 1, 2 y 3
(D) 2, 3 y 4

Respuesta: (C)
Explicación: La cuarta optimización generalmente no se usa, reduce lo peor complejidad del tiempo del caso a O(nLogn), pero las constantes ocultas son muy altas.
Cuestionario de esta pregunta