Algoritmos | Clasificación | Pregunta 5

Dada una array no ordenada. La array tiene esta propiedad de que cada elemento en la array está a una distancia máxima de k de su posición en la array ordenada, donde k es un número entero positivo más pequeño que el tamaño de la array. ¿Qué algoritmo de clasificación se puede modificar fácilmente para clasificar esta array y cuál es la complejidad de tiempo obtenible?
(A) Clasificación por inserción con complejidad de tiempo O(kn)
(B) Clasificación por montón con complejidad de tiempo O(nLogk)
(C) Clasificación rápida con complejidad de tiempo O(kLogk)
(D) Clasificación por fusión con complejidad de tiempo O(kLogk)

Respuesta: (B)
Explicación: 1) para ordenar la array, primero cree un montón mínimo con los primeros k + 1 elementos y una array separada como array resultante.
2) porque los elementos están a una distancia máxima de k de la posición original, por lo que se garantiza que el elemento más pequeño estará en estos elementos K+1.
3) elimine el elemento más pequeño del montón mínimo (extraer min) y colóquelo en la array de resultados.
4) Ahora, inserte otro elemento de la array sin clasificar en el montón medio, ahora, el segundo elemento más pequeño estará en esto, realice extract min y continúe este proceso hasta que no haya más elementos en la array sin clasificar. finalmente, use la ordenación de montón simple para los elementos restantes

Complejidad del tiempo

————————

1) O(k) para construir el montón mínimo inicial

2) O((nk)logk) para los elementos restantes…

3) 0(1) para extraer min

entonces, en general, O (k) + O ((nk) logk) + 0 (1) = O (nlogk)
Cuestionario de esta pregunta