ISRO | CS ISRO 2018 | Pregunta 17

De los siguientes algoritmos de clasificación, ¿cuál tiene un tiempo de ejecución que depende menos de la ordenación inicial de la entrada?

(A) Ordenación por fusión
(B) Ordenación por inserción
(C) Ordenación por selección
(D) Ordenación rápida

Respuesta: (A)
Explicación: En la ordenación por inserción, si la array ya está ordenada, toma O(n) y si está ordenada inversamente, entonces se necesita O(n ² ) para ordenar la array. En Ordenación rápida, si la array ya está ordenada o si está ordenada inversamente, toma O(n ² ). El mejor y el peor de los casos de rendimiento de Selección es O(n ² ) solamente. Pero si la array ya está ordenada, se realizan menos intercambios. En la ordenación por combinación, la complejidad del tiempo es O (nlogn) para todos los casos y el rendimiento se ve menos afectado en el orden de la secuencia de entrada.

Entonces, la opción (A) es correcta.
Cuestionario de esta pregunta