Este método de ordenación ubica el elemento con el mayor valor de la lista y una vez ubicado se intercambian los valores de este elemento con el ultimo elemento de la lista, de esta manera (al igual que sucedia con e metodo de Burbuja), el ultimo elemento queda con el valor correcto (el mayor).
El procedimiento descrito en el anterior parrafo constituye en sí el metodo de Selección. Ahora para los restantes elementos de la lista se repite el procedimiento pero sin tomar en cuenta el ultimo elemento, luego se vuelve a repetir sin tomar en cuenta los dos ultimos elementos y se continua así hasta que en la lista sólo queda un elemento.
Debido a que sólo se efectua un intercambio cada vez que se repite el método y tomando en cuenta que el intercambio de valores es la operacion que mas tiempo consume en los metodos de ordenación este método suele ser un tanto mas rapido que el metodo de la Burbuja. Sin embargo, en este metodo no existe ningun indicador que nos permita saber si la lista queda ordenada en algun momento durante el proceso, de manera que el método continua hasta que solo queda un elemento, incluso cuando la lista ya esta ordenada.
Ejemplo: Teniendo el siguiente vector: x1, x2, x3, x4, x5 con valores:
| 8 | 6 | 9 | 5 | 2 |
Analizamos la lista y vemos que el mayor valor (9) se encuentra en la posicion 3, por lo tanto intercambiamos valores de los elementos x3 y x5
Ahora repetimos el procedimiento sin tomar en cuenta el ultimo elemento (pues ya tiene el valor correcto). Ahora vemos que el mayor valor (8) se encuentra en la posicion 1, por tanto intercambiamos los valores de los elementos x1 y x4
con lo que el penultimo elemento (x4) queda con el valor correcto. Repetimos nuevamente el procedimiento pero sin tomar en cuenta los dos ultimos elementos. Vemos ahora que el mayor valor (6) esta en la posicion 2, por tanto intercambiamos los valores de los elementos x2 y x3
Con lo que x3 queda con el valor correcto. Repetimos una vez mas el procedimiento pero sin tomar en cuenta los elementos x3,x4,x5. Vemos ahora que el mayor valor (5) se encuentra en la posicion 1, por tanto intercambiamos los valores x1 y x2.
Entonces x2 tambien queda con el valor correcto, como ahora solo queda un elemento (x1) el proceso concluye y la lista ya esta ordena.
Codigo Java: La clase escrita en Java se llama "Seleccion.java"
Nota: la linea de codigo (33) solo nos sirve para mostrar el ciclo en pantalla, no es necesario.
Nota2: el metodo Mostrar(int[] v) prepara el vector en un String de la forma |0|1|2|3|4|5| para su impresion en pantalla,
Implementacion:
El metodo generarlista(n) , genera una lista de enteros dado un rango.
Resultado:
| 8 | 6 | 2 | 5 | 9 |
Ahora repetimos el procedimiento sin tomar en cuenta el ultimo elemento (pues ya tiene el valor correcto). Ahora vemos que el mayor valor (8) se encuentra en la posicion 1, por tanto intercambiamos los valores de los elementos x1 y x4
| 5 | 6 | 2 | 8 | 9 |
con lo que el penultimo elemento (x4) queda con el valor correcto. Repetimos nuevamente el procedimiento pero sin tomar en cuenta los dos ultimos elementos. Vemos ahora que el mayor valor (6) esta en la posicion 2, por tanto intercambiamos los valores de los elementos x2 y x3
| 5 | 2 | 6 | 8 | 9 |
Con lo que x3 queda con el valor correcto. Repetimos una vez mas el procedimiento pero sin tomar en cuenta los elementos x3,x4,x5. Vemos ahora que el mayor valor (5) se encuentra en la posicion 1, por tanto intercambiamos los valores x1 y x2.
| 2 | 5 | 6 | 8 | 9 |
Entonces x2 tambien queda con el valor correcto, como ahora solo queda un elemento (x1) el proceso concluye y la lista ya esta ordena.
Codigo Java: La clase escrita en Java se llama "Seleccion.java"
01 /** 02 * @web http://jc-mouse.blogspot.com/ 03 * @author Mouse 04 */ 05 public class seleccion { 06 private int[] vector; 07 private int elementos; 08 09 public seleccion (){} 10 11 public int[] ordenar(int[] v){ 12 this.vector=v; 13 elementos = vector.length; 14 //se toma como valor mayor el ultimo elemento del vector "n-1" 15 int mayor = vector[elementos-1];//ojo: en java el array empieza en "0" 16 int pos = elementos-1; 17 int aux; 18 //se repite el ciclo hasta que quede un solo elemento 19 while(elementos > 1) { 20 //se recorre todos los elementos del vector 21 for(int i=0; i<elementos;i++){ 22 //se busca el elemento mayor 23 if(vector[i]>mayor){ 24 mayor = vector[i]; 25 pos = i; 26 } 27 } 28 // se intercambian valores, el valor mayor encontrado se hubica en 29 // la ultima posicion del vector 30 aux = vector[elementos-1]; 31 vector[elementos-1] = mayor; 32 vector[pos] = aux; 33 System.out.println("orden de ciclo : "+ Mostrar(vector)); 34 //se resta en uno la cantidad de elementos 35 elementos--; 36 //se toma como valor mayor el ultimo elemento del vector 37 mayor = vector[elementos-1]; 38 pos = elementos-1; 39 } 40 return vector; 41 } 42 43 //para imprimir el array de la forma | 0 | 1 | 2 | 3 | 4 | 44 public String Mostrar(int[] v){ 45 String s=" | "; 46 for (int i=0; i < v.length; i++){ 47 s += v[i] + " | "; 48 } 49 return s; 50 } 51 }
Nota2: el metodo Mostrar(int[] v) prepara el vector en un String de la forma |0|1|2|3|4|5| para su impresion en pantalla,
Implementacion:
01 import java.util.Random; 02 /** 03 * @web http://jc-mouse.blogspot.com/ 04 * @author Mouse 05 */ 06 public class Main { 07 08 public static void main(String[] args) { 09 //creamos un array y llenamos este con numeros al azar 10 int[] c = null ; 11 c = generarlista(5); 12 seleccion s = new seleccion(); 13 System.out.println("ORIGINAL : "+ s.Mostrar(c)); 14 System.out.println("ORDENADO : "+ s.Mostrar(s.ordenar(c))); 15 } 16 17 //genera un array de n elementos enteros 18 public static int[] generarlista(int n){ 19 int[] v = new int[n]; 20 Random rand = new Random(); 21 for (int i=0; i<v.length; i++){ 22 v[i]=rand.nextInt(10); 23 } 24 return v; 25 } 26 }
El metodo generarlista(n) , genera una lista de enteros dado un rango.
Resultado:
FIN
No hay comentarios:
Publicar un comentario