La respuesta depende de la estrategia para elegir el pivote. En las primeras versiones de Quick Sort donde el elemento más a la izquierda (o más a la derecha) se elige como pivote, lo peor ocurre en los siguientes casos.
1) La array ya está ordenada en el mismo orden.
2) La array ya está ordenada en orden inverso.
3) Todos los elementos son iguales (un caso especial de los casos 1 y 2)
Dado que estos casos son muy comunes para los casos de uso, el problema se resolvió fácilmente eligiendo un índice aleatorio para el pivote, eligiendo el índice medio de la partición o (especialmente para particiones más largas) eligiendo la mediana del primero, medio y último elemento del tabique para el pivote. Con estas modificaciones, el peor caso de Quicksort tiene menos posibilidades de ocurrir, pero aún puede ocurrir el peor caso si la array de entrada es tal que el elemento máximo (o mínimo) siempre se elige como pivote.
Referencias:
http://en.wikipedia.org/wiki/Quicksort
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA