PUERTA | PUERTA-CS-2009 | Pregunta 10

¿Cuál es el número de intercambios necesarios para clasificar n elementos utilizando la clasificación por selección, en el peor de los casos?
(A)  (n)
(B)  (n log n)
(C)  (n^2 )
(D)  (n^2 log n)
(A) Theta(n)
(B) Theta(nLogn)
(C) Theta (n*n)
(D) Theta(n*nLogn)

Respuesta: (A)
Explicación: Aquí está el algoritmo de clasificación de selección para clasificar en orden ascendente.

   1. Find the minimum value in the list
   2. Swap it with the value in the first position
   3. Repeat the steps above for the remainder of the list (starting at
      the second position and advancing each time)

Como podemos ver en el algoritmo, la ordenación por selección realiza el intercambio solo después de encontrar la posición adecuada del elemento seleccionado actual. Entonces, hay intercambios O (n) realizados en la clasificación por selección.
Debido a que los intercambios requieren escribir en la array, la ordenación por selección es preferible si escribir en la memoria es significativamente más costoso que leer. Este suele ser el caso si los elementos son enormes pero las teclas son pequeñas. Otro ejemplo donde los tiempos de escritura son cruciales es una array almacenada en EEPROM o Flash. No hay otro algoritmo con menos movimiento de datos.

Referencias:
http://en.wikipedia.org/wiki/Selection_sort
Cuestionario de esta pregunta