Metodo Por Seleccion

METODO POR SELECCIÓN

El ordenamiento por selección es un algoritmo de ordenamiento que requiere operaciones para ordenar una lista de n elementos.

DESCRIPCION DEL ALGORITMO

VSu funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista

• Intercambiarlo con el primero

• Buscar el siguiente 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 elemento de 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:

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista

• Intercambiarlo con el primero

• Buscar el siguiente 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 elemento de 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

mínimo = i;

para j=i+1 hasta n

si lista[j] < lista[mínimo] entonces

mínimo = j /* (!) */

fin si

fin para

intercambiar(lista[i], lista[mínimo])

fin para

La idea básica es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e

intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el

siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta

que el último elemento ha sido transferido a su posición correcta.

El algoritmo de ordenación depende a su vez del algoritmo necesario para localizar el componente

mayor (menor) de un array. Es un proceso muy similar al método de la burbuja pero haciendo más

eficiente la búsqueda y evitando intercambios innecesarios.

Consideremos el mismo arreglo del ejemplo anterior { 7, 2, 8, 3, 5, 1 }. El proceso sería de la

siguiente manera:

1ra iteración, i permanece fijo en la casilla 0 y j se incrementa hasta llegar al último elemento:

{ 7, 2, 8, 3, 5, 1 } k = 0, j = 1, cambio k = j ya que en j esta el menor

{ 7, 2, 8, 3, 5, 1 } k = 1, j = 2, no genera cambio

{ 7, 2, 8, 3, 5, 1 } k = 1, j = 3, no genera cambio

{ 7, 2, 8, 3, 5, 1 } k = 1, j = 4, no genera cambio

{ 7, 2, 8, 3, 5, 1 } k = 1, j = 5, cambio k = j ya que en j esta el menor, genera { 1, 2, 8, 3, 5, 7 }

2da iteración, i permanece fijo en la casilla 1 y j se incrementa hasta llegar al último elemento:

{ 1, 2, 8, 3, 5, 7 } k = 1, j = 2 - 5, no genera cambios

3ra iteración, i permanece fijo en la casilla 2 y j se incrementa hasta llegar al último elemento:

{ 1, 2,

...