Sea P un programa QuickSort para ordenar números en orden ascendente usando el primer elemento como pivote. Sean t1 y t2 el número de comparaciones realizadas por P para las entradas {1, 2, 3, 4, 5} y {4, 1, 5, 3, 2} respectivamente. ¿Cuál de los siguientes se cumple?
(A) t1 = 5
(B) t1 < t2
(C) t1 > t2
(D) t1 = t2
Respuesta: (C)
Explicación: cuando se elige el primer elemento o el último elemento como pivote, el peor de los casos de Quick Sort ocurre para las arrays ordenadas.
En cada paso de clasificación rápida, los números se dividen según la siguiente recurrencia.
T(n) = T(n-1) + O(n)
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