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

Suponga que los algoritmos considerados aquí clasifican las secuencias de entrada en orden ascendente. Si la entrada ya está en orden ascendente, ¿cuáles de los siguientes son VERDADEROS?

I.   Quicksort runs in Θ(n2) time
II.  Bubblesort runs in Θ(n2) time
III. Mergesort runs in  Θ(n) time
IV.  Insertion sort runs in  Θ(n) time 

(A) Solo I y II
(B) Solo I y III
(C) Solo II y IV
(D) Solo I y IV

Respuesta: (D)
Explicación: I. Dada una array en orden ascendente, la relación de recurrencia para el número total de las comparaciones para ordenación rápida serán
T(n) = T(n-1)+O(n) //el algoritmo de partición tomará comparaciones O(n) en cualquier caso.
= O(n^2)

II. Bubble Sort se ejecuta en Θ(n^2) tiempo

Si una array está en orden ascendente, podríamos hacer una pequeña modificación en Bubble Sort Inner for loop que es responsable de burbujear el k-ésimo elemento más grande hasta el final en la k-ésima iteración. Siempre que no haya un intercambio después de completar el bucle for interno de la ordenación de burbujas en cualquier iteración, podemos declarar que la array está ordenada en caso de que la ordenación de burbujas tome O (n) tiempo en el mejor de los casos.

tercero Merge Sort se ejecuta en Θ(n) tiempo.
Merge Sort se basa en el paradigma Divide and Conquer para ordenar una array y no existe tal entrada de peor o mejor caso para la ordenación de combinación. Para cualquier secuencia, la complejidad del tiempo estará dada por la siguiente relación de recurrencia,

T(n) = 2T(n/2) + Θ(n) // El algoritmo de combinación en el lugar tomará Θ(n) debido a la copia de una array completa.
= Θ(nlogn)

IV. La ordenación por inserción se ejecuta en tiempo Θ(n)

Cada vez que se agregue un nuevo elemento que será mayor que todos los elementos de la sub-array ordenada intermedia (porque la array dada está ordenada), no habrá ningún intercambio sino una única comparación. En n-1 pasadas tendremos 0 intercambios y n-1 comparaciones.
Complejidad de tiempo total = O(n) // Comparaciones N-1

Esta solución es aportada por Pranjul Ahuja

////
Para una array ya ordenada en orden ascendente,
Quicksort tiene una complejidad Θ(n ² ) [Worst Case]
​​Bubblesort tiene una complejidad Θ(n) [Best Case]
​​Mergesort tiene una complejidad Θ (n log n) [Cualquier caso]
Insertsort tiene una complejidad Θ(n) [Mejor caso]

Cuestionario de esta pregunta