PUERTA | GATE-CS-2014-(Conjunto-3) | Pregunta 24

Tienes una array de n elementos. Suponga que implementa la ordenación rápida eligiendo siempre el elemento central de la array como pivote. Entonces, el límite superior más ajustado para el desempeño en el peor de los casos es
(A) O(n ² )
(B) O(nLogn)
(C) Theta(nLogn)
(D) O(n ³ )

Respuesta: (A)
Explicación: Para cualquier entrada, hay algunas permutaciones para las cuales el peor de los casos será O(n ² ) . En algunos casos, elegir el elemento intermedio minimiza las posibilidades de encontrar  O(n ² ), pero en el peor de los casos puede ir a  O(n ² ). Cualquiera que sea el elemento que tomemos como pivote, ya sea el primero o el medio, el peor de los casos será  O(n ² )  ya que el pivote está fijo en su posición. Mientras que elegir un pivote aleatorio minimiza las posibilidades de encontrar el peor de los casos, es decir,  O (n ² ).

Consulte este  artículo sobre Clasificación rápida.
Cuestionario de esta pregunta