¿Cuál es el peor caso de quicksort y cuándo ocurre?
Opciones
- O(n log n) de media, y nunca peor con ninguna entrada
- O(n²) con pivotes malos, como con una entrada ordenada (Opción correcta)
- O(n) cuando el array de entrada ya está ordenado
- O(log n) cuando el pivote siempre es la mediana
Respuesta
O(n²), con pivotes malos de forma constante (por ejemplo el primer elemento en una entrada ya ordenada)
Por qué
Quicksort elige un pivote, pone los elementos menores a su izquierda y los mayores a su derecha, y luego ordena cada lado.
Si el pivote es siempre el menor o el mayor (por ejemplo elegir el primer elemento de una lista ya ordenada), un lado queda vacío cada vez, así que hace n + (n-1) + ... pasos = O(n²).
Los pivotes aleatorios o la mediana de tres hacen eso muy improbable. El sorted de Python usa Timsort, que es O(n log n) en el peor caso.
Recuerda
Quicksort: O(n log n) de media, O(n²) con pivotes malos.