Método de Selección [Algoritmo de Ordenación]

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

| 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 }

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:

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

continue reading

Metodo de la burbuja (bubble sort java)

Este metodo nos permite ordenar ascendentemente los elementos de una lista , se comienza comparando los dos primeros elementos  y si el valor del primer elemento es mayor que el segundo  entonces se intercambian valores. Luego se procede  de la misma manera con el segundo y tercer elemento, posteriormente con el tercer y cuarto elemento y asi sucesivamente hasta llegar al ultimo par de elementos, de esta manera en el ultimo elemento siempre queda el mayor valor de la lista.Por lo tanto el ultimo elemento de la lista siempre queda con el valor correcto, el mayor.

Si se quiere ordenar una lista descendentemente, entonces se aplica el mismo procedimiento, solo que ahora al comparar se pregunta si el valor  del primer elemento es menor que el segundo.
Nuestra clase se llama burbuja.java y contiene el metodo ordenar asi como un metodo para imprimir la lista.

/**
 * @web http://jc-mouse.blogspot.com/
 * @author mouse
 */

public class burbuja {
    int[] vector ;
    int elementos=0;
    boolean bandera=true;
    
    public burbuja (int[] v){
        this.vector=v;
    }    

    public int[] ordenar(){
        int p1;
        int p2;        
        int y=0;
        bandera=true;
        elementos = vector.length;
        while((elementos > 1) && (bandera==true) )
        {
            y=0;
            p1 = vector[y];
            p2 = vector[y+1];
            elementos--;
            bandera=false;
            for(int i=0; i < elementos; i++){                                
                if (p1>p2){                   
                    vector[i]=p2;
                    vector[i+1]=p1;
                    bandera=true;                      
                }//fin de si         
                System.out.println("ordenando: "+ Mostrar(vector));
                y++;
                if (y < elementos){                    
                    p1 = vector[y];
                    p2 = vector[y+1];                
                }                    
            }//fin for                       
        }//fin de mientras
        return vector;
    }
    //para imprimir el array
    public String Mostrar(int[] v){
        String s=" | ";
        for (int i=0; i < v.length; i++){
            s += v[i] + " | ";
        }
        return s;
    }    
}

Para implementar esta clase, el main debe contener el siguiente codigo:

public class Main {  
   
    public static void main(String[] args) {         
        //creamos un array y llenamos este con numeros al azar
        int[] c = null ;        
        c = generarlista(5);        
        //creamos el objeto burbuja y mostramos
        burbuja b = new burbuja(c);                
        System.out.println("ORIGINAL : "+ b.Mostrar(c));        
        System.out.println("ORDENADO : "+ b.Mostrar(b.ordenar()));
        
    }
    //genera un array de n elementos
    public static int[] generarlista(int n){        
        int[] v = new int[n];
        Random rand = new Random();
        for (int i=0; i<v.length; i++){
            v[i]=rand.nextInt(1000);
        }   
        return v;
    }    
}

Aparte se tiene un metodo para generar un array de enteros "generarlista()" el cual utiliza un random para llenar un array con "n" numeros enteros. este metodo nos sirve para realizar la prueba mas facilmente.

Como se puede observar en el resultado este metodo no es eficiente, ya que el tiempo requerido para ordenar listas grandes se incrementa geometricamente, razon por la cual solo resulta de utilizad para ordenar listas pequeñas (ni se te ocurra probar este algoritmo con un 1000000 de elementos), ademas otra desventaja que presenta es el de no tener un parametro de control que nos indique que la lista ya esta ordenana (incluso si la lista esta ordenada desde el principio), el procedimiento se llevara a cabo n-1 veces.

continue reading