Seleccion directa

Selección Directa (SelectionSort)
2010
3 C ISC
08/12/2010

¿QUÉ ES?
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
 El método de ordenación por selección directa es más eficiente que los métodos analizados anteriormente.
Es un algoritmo relativamente sencillo y uno de los másfáciles de recordar e implementar.
Pero, aunque su comportamiento es mejor que el de aquéllos y su programación es fácil y comprensible, no es recomendable utilizarlo cuando el número de elementos del arreglo es medio grande.
 
CARACTERÍSTICAS.

    La idea básica de este algoritmo consiste en buscar el menor elemento en el arreglo y colocarlo en primera posición. Luego se busca el segundoelemento más pequeño del arreglo y se lo coloca en segunda posición. El proceso continua hasta que todos los elementos del arreglo hayan sido ordenados. El método se basa en los siguientes principios:

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterioclaro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).

Es un algoritmo no estable de ordenación interna y su complejidad temporal en el peor caso es de O(n2) y en el mejor caso -que el array ya esté totalmente ordenado- pues también es Ω(n2) siendo n el tamaño del array a ordenar... el caso es que éste algoritmo siempre hace el mismonúmero de comparaciones e intercambios para un n dado... así que no aprovecha una posible ordenación parcial del array.

El algoritmo consiste en realizar varias pasadas sobre el array, logrando que en cada pasada el elemento de menor valor se coloque al principio del array en un solo intercambio.
En cada pasada se recorre la parte no ordenada del array realizando comparaciones con objetode buscar el elemento de menor valor. Una vez localizado, se intercambia por el primer elemento de la parte no ordenada, y entonces ya está en orden.
Por eso, se suele implementar con dos bucles, uno anidado dentro del otro. El bucle exterior realiza las pasadas y el interior localiza el menor elemento.

VENTAJAS

En cuanto a la complejidad espacial, es muy ahorrativo: tan solo necesita unavariable temporal para realizar los intercambios, así que su gasto de memoria es constante, sea cual sea el tamaño del array. Aunque se suele utilizar para ordenación interna, puede usarse para ordenación externa si nos es imprescindible una complejidad espacial constante y muy baja. Esa situación no suele darse, excepto, quizá, en pequeños dispositivos dotados de una cantidad de memoria principal muymuy reducida y en los que además, los datos estén en un soporte cuya lectura sea mucho más rápida que la escritura.

DESVENTAJAS
A efectos prácticos, no suele dar resultados buenos si se compara con otros métodos de ordenación. Realiza una enorme cantidad de comparaciones, pero en contrapartida, muy pocos intercambios. Eso hace que su utilización se restrinja en general a dos situaciones: obien necesitamos un algoritmo sencillito para ordenar unos pocos datos y cogemos éste mismo que no está mal y es facil de recordar, o bien tenemos una situación en la cual escribir en el array es mucho más gravoso que leer, como puede ser un escenario en el que intervengan determinados dispositivos de almacenamiento o memorias tipo flash, eeprom, etc. para el soporte de los datos.
Por otro lado,debido al reducido número de intercambios que realiza el algoritmo, no es posible aprovecharse de una mejora de velocidad en aquellos casos en los que el array esté semi-ordenado o incluso totalmente ordenado. El algoritmo siempre hace las mismas comparaciones e intercambios.
Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su...