Metodos de ordenamiento

Ordenamiento por selección
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda

Animación del Selection SortEl ordenamiento por selección (Selection Sort en inglés) es unalgoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

Buscar el mínimo elemento de la lista
Intercambiarlo con el primeroBuscar el mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:

Buscar el mínimo elemento entre una posición i y el final de la lista
Intercambiar el mínimo con el elementode la posición i
De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1
minimo = i;
para j=i+1 hasta nsi lista[j] < lista[minimo] entonces
minimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[minimo])
fin para
Este algoritmo mejora ligeramente elalgoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operaciónintercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyerapor intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).

Otra desventaja de este algoritmo respecto aotros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbujase requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos...