Ordenación por selección

Se trata de ordenar un arreglo formado por n enteros. Para esto el algoritmo de selección va seleccionando los elementos menores al actual y los intercambia.

Procedimiento Ordenación por Selección

( var T [ 1 .. n ] )
para i := 1 hasta n – 1 hacer minj := i ;
minx := T [ i ] ;
para j := i + 1 hasta n hacer si T [ j ] < minx entonces
minj := j ; minx := T [ j ]
fin si fin para ;
T [ minj ] := T [ i ] ; T [ i ] := minx
fin para
fin procedimiento

n es una variable o constante global que indica el tamaño del arreglo.

Al igual que en el caso anterior los resultados obtenidos dependen de la inicialización del arreglo de datos. Este arreglo puede estar inicializado de forma creciente, decreciente o aleatoriamente.

El peor caso ocurre cuando el arreglo está inicializado descendentemente. El mejor caso ocurre tanto para la inicialización ascendente como aleatoria.

Para este algoritmo cabe destacar que en comparación con la ordenación por inserción los tiempos fluctúan mucho menos entre las diferentes inicializaciones del arreglo. Esto se debe a que este algoritmo (el de selección) realiza prácticamente el mismo número de operaciones en cualquier inicialización del arreglo.

Se ha calculado empíricamente la complejidad para este algoritmo, y, se ha obtenido que para cualquier inicialización del arreglo de datos el algoritmo tenga una complejidad cuadrática O(n²).

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM