PUERTA | GATE-CS-2016 (Conjunto 1) | Pregunta 23

Los peores tiempos de ejecución de la ordenación por inserción, la ordenación por fusión y la ordenación rápida, respectivamente, son:

(A) Θ(n log n), Θ(n log n) y Θ(n ² )

(B) Θ(n ² ), Θ(n ² ) y Θ(n Log n)

(C) Θ(n ² ), Θ(n log n) y Θ(n log n)

(D) Θ(n ² ), Θ(n log n) y Θ(n ² )

Respuesta: (D)
Explicación:

• La ordenación por inserción toma Θ(n ² ) en el peor de los casos, ya que necesitamos ejecutar dos bucles. El bucle exterior es necesario para elegir uno por uno un elemento que se insertará en la posición correcta. El bucle interno se usa para dos cosas, para encontrar la posición del elemento que se va a insertar y para mover todos los elementos mayores ordenados una posición hacia adelante. Por lo tanto, la fórmula recursiva del peor de los casos es T(n) = T(n-1) + Θ(n).
• Merge Sort toma tiempo Θ(n Log n) en todos los casos. Siempre dividimos la array en dos mitades, ordenamos las dos mitades y las fusionamos. La fórmula recursiva es T(n) = 2T(n/2) + Θ(n).
• QuickSort toma Θ(n ² ) en el peor de los casos. En QuickSort, tomamos un elemento como pivote y dividimos la array a su alrededor. En el peor de los casos, el elemento seleccionado siempre es un elemento de esquina y la fórmula recursiva se convierte en T(n) = T(n-1) + Θ(n). Un escenario de ejemplo cuando ocurre el peor de los casos es que las arrays se ordenan y nuestro código siempre elige un elemento de esquina como pivote.

 
Cuestionario de esta pregunta