bubblesort arraylist

Iniciado por Beginner Web, 13 Abril 2019, 21:02 PM

0 Miembros y 1 Visitante están viendo este tema.

Beginner Web

Hola como puedo hacer para ordenar un arraylist de objetos por nombre? Intente el metodo de la burbuja pero no pasa nada  :huh:

Código (java) [Seleccionar]
public void ordenar() {
       Persona cambio;
       boolean ordenado = true;
       while (ordenado == true) {
           ordenado = false;
           for (int i = 0; i < personas.size() - 1; i++) {
               if (personas.get(i).getNombre().compareTo(personas.get(i + 1).getNombre()) > 0) {
                   cambio = personas.get(i);
                   personas.set(i, personas.get(i + 1));
                   personas.set(i + 1, cambio);
                   ordenado = true;
               }
           }
       }
   }
7w7

Serapis

Los algoritmos de ordenamiento, suelen tener al menos dos bucles (uno dentro de otro).
Tu solo has puesto un bucle, luego al término del mismo, tan solo habrías obtenido el menor/mayor de todos ellos y por tanto solo habrías colocado la 1ª pieza. falta hacer lo mismo para los x-1 piezas restantes...

Sean 20 elementos a ordenar... (0 a 19)

bucle para j desde 0 hasta 20-2  <----- ojo, 2 ítems menos, solo debe llegar al 18, para que la última comparaci´´on sea el 18 con el 19, resulta redundante comparar cada vez el 19 con el 19.
   temp = item(j)
   // j + 1, por que es redundante comparar 5 con 5, 8 con 8, 320 con 320.
   // Igualmente como a la salida del bucle iterno cada vez 'j' ya está ordenado, es redundante reiniciar el bucle interno desde 0.
   bucle para k desde j+1 hasta 20-1  <--- este debe llegar hasta 19.
       si (item(k) > temp) entonces
          intercambiar item(k) con temp
       fin si
   siguiente
   item(j) = temp
siguiente

Beginner Web

7w7

rub'n

#3
Cita de: Beginner Web en 13 Abril 2019, 21:02 PM
Hola como puedo hacer para ordenar un arraylist de objetos por nombre? Intente el metodo de la burbuja pero no pasa nada  :huh:

Código (java) [Seleccionar]
public void ordenar() {
       Persona cambio;
       boolean ordenado = true;
       while (ordenado == true) {
           ordenado = false;
           for (int i = 0; i < personas.size() - 1; i++) {
               if (personas.get(i).getNombre().compareTo(personas.get(i + 1).getNombre()) > 0) {
                   cambio = personas.get(i);
                   personas.set(i, personas.get(i + 1));
                   personas.set(i + 1, cambio);
                   ordenado = true;
               }
           }
       }
   }


Tu algoritmo funciona, ordena de manera ascendente que estarás haciendo cuando lo invocas?

hagamosle caso a NEBIRE

Bean Persona

Código (java) [Seleccionar]
import java.util.Objects;

public class Persona {

   private String nombre;
   private int edad;
   private String apellido;
   private boolean esAlto;
   private double peso;

   public String getNombre() {
       return nombre;
   }

   public void setNombre(String nombre) {
       this.nombre = nombre;
   }

   public int getEdad() {
       return edad;
   }

   public void setEdad(int edad) {
       this.edad = edad;
   }

   public String getApellido() {
       return apellido;
   }

   public void setApellido(String apellido) {
       this.apellido = apellido;
   }

   public boolean isEsAlto() {
       return esAlto;
   }

   public void setEsAlto(boolean esAlto) {
       this.esAlto = esAlto;
   }

   public double getPeso() {
       return peso;
   }

   public void setPeso(double peso) {
       this.peso = peso;
   }

   @Override
   public boolean equals(Object o) {
       if (this == o) return true;
       if (!(o instanceof Persona)) return false;
       Persona persona = (Persona) o;
       return edad == persona.edad &&
               esAlto == persona.esAlto &&
               Double.compare(persona.peso, peso) == 0 &&
               Objects.equals(nombre, persona.nombre) &&
               Objects.equals(apellido, persona.apellido);
   }

   @Override
   public int hashCode() {
       return Objects.hash(nombre, edad, apellido, esAlto, peso);
   }

   @Override
   public String toString() {
       final StringBuilder sb = new StringBuilder("\nPersona");
       sb.append("\nnombre='").append(nombre).append("\n");
       sb.append(", edad=").append(edad);
       sb.append(", apellido='").append(apellido).append("\n");
       sb.append(", esAlto=").append(esAlto);
       sb.append(", peso=").append(peso);
       sb.append("]");
       return sb.toString();
   }
}


Código (java) [Seleccionar]
import java.util.*;

/**
* @rubn ,@NEBIRE, @Ana XD
*/
public class OrdenarPersonaPorNombre {

   private List<Persona> personaList = new ArrayList<>();
   private static final String TITLE = "Personas Ordenadas Alfabeticamente...";

  OrdenarPersonaPorNombre () {
       fillList();
       ordenar();
   }

   private void fillList() {
       final Persona persona = new Persona();
       persona.setNombre("Raul");
       persona.setEdad(30);
       persona.setApellido("Gonzales");
       persona.setPeso(56);
       persona.setEsAlto(Boolean.TRUE);

       final Persona persona2 = new Persona();
       persona2.setNombre("Josefina");
       persona2.setEdad(40);
       persona2.setApellido("Sinforoza");
       persona2.setPeso(60);
       persona2.setEsAlto(Boolean.FALSE);

       final Persona persona3 = new Persona();
       persona3.setNombre("Ana");
       persona3.setEdad(14);
       persona3.setApellido("Begginer  Web");
       persona3.setPeso(45);
       persona3.setEsAlto(Boolean.FALSE);

       final Persona persona4 = new Persona();
       persona4.setNombre("Babel");
       persona4.setEdad(23);
       persona4.setApellido("Bhahal");
       persona4.setPeso(55);
       persona4.setEsAlto(Boolean.TRUE);

       final Persona persona5 = new Persona();
       persona5.setNombre("Mega");
       persona5.setEdad(100);
       persona5.setApellido("Man");
       persona5.setPeso(200);
       persona5.setEsAlto(Boolean.TRUE);

       personaList.add(persona);
       personaList.add(persona2);
       personaList.add(persona3);
       personaList.add(persona4);
       personaList.add(persona5);
   }

   //con java 7
   private void ordenar() {
      /* for(int f=0; f<personaList.size();f++) {
           for(int c=0; c<(personaList.size() - 1) - f; c++) {
               //personaList.size() -1, para evitar IndexOutBoundException
               //que es una exception que se produce en tiempo de ejecucion por index fuera de rango
                   if(personaList.get(c).getNombre().compareTo( personaList.get(c+1).getNombre()) > 0) {
                       final String auxiliar = personaList.get(c).getNombre();
                       personaList.get(c).setNombre(personaList.get(c+1).getNombre());
                       personaList.get(c+1).setNombre(auxiliar);
                   }
           }
       }*/

      Collections.sort(personaList);

      System.out.println(TITLE);
      for (int f=0; f<personaList.size(); f++) {
          System.out.println(personaList.get(f));
      }

   }

   //con java.util.Stream
   private void ordenarConStreams() {

       System.out.println(TITLE);
       personaList.stream()
               .sorted(Comparator.comparing(Persona::getNombre))
               .forEach(System.out::println);

   }

   public static void main(String ...blablabla) {
       new OrdenarPersonaPorNombre ();
   }
}


Output_
Código (bash) [Seleccionar]
Personas Ordenadas Alfabeticamente...

Persona
nombre='Ana
, edad=14, apellido='Begginer  Web
, esAlto=false, peso=45.0]

Persona
nombre='Babel
, edad=23, apellido='Bhahal
, esAlto=true, peso=55.0]

Persona
nombre='Josefina
, edad=40, apellido='Sinforoza
, esAlto=false, peso=60.0]

Persona
nombre='Raul
, edad=30, apellido='Gonzales
, esAlto=true, peso=56.0]

Process finished with exit code 0


Te he añadido en la linea 73 como hacer también con la clase Collections y su método sort

pero debemos implementar la interface Comparable<T>

cambiando a Persona



Código (java) [Seleccionar]


public class Persona implements Comparable<Persona> {



implementando al método

Código (java) [Seleccionar]
public int compareTo(T o);

Código (java) [Seleccionar]

@Override
public int compareTo(Persona o) {
   final Persona p1 = o;
   return this.getNombre().compareTo(p1.getNombre());
}


Quedando
Código (java) [Seleccionar]

import java.util.Objects;

public class Persona implements Comparable<Persona> {

   private String nombre;
   private int edad;
   private String apellido;
   private boolean esAlto;
   private double peso;
   
   public String getNombre() {
       return nombre;
   }

   public void setNombre(String nombre) {
       this.nombre = nombre;
   }

   public int getEdad() {
       return edad;
   }

   public void setEdad(int edad) {
       this.edad = edad;
   }

   public String getApellido() {
       return apellido;
   }

   public void setApellido(String apellido) {
       this.apellido = apellido;
   }

   public boolean isEsAlto() {
       return esAlto;
   }

   public void setEsAlto(boolean esAlto) {
       this.esAlto = esAlto;
   }

   public double getPeso() {
       return peso;
   }

   public void setPeso(double peso) {
       this.peso = peso;
   }


   @Override
   public boolean equals(Object o) {
       if (this == o) return true;
       if (!(o instanceof Persona)) return false;
       Persona persona = (Persona) o;
       return edad == persona.edad &&
               esAlto == persona.esAlto &&
               Double.compare(persona.peso, peso) == 0 &&
               Objects.equals(nombre, persona.nombre) &&
               Objects.equals(apellido, persona.apellido);
   }

   @Override
   public int hashCode() {
       return Objects.hash(nombre, edad, apellido, esAlto, peso);
   }

   @Override
   public String toString() {
       final StringBuilder sb = new StringBuilder("\nPersona");
       sb.append("\nnombre='").append(nombre).append("\n");
       sb.append(", edad=").append(edad);
       sb.append(", apellido='").append(apellido).append("\n");
       sb.append(", esAlto=").append(esAlto);
       sb.append(", peso=").append(peso);
       sb.append("]");
       return sb.toString();
   }

   @Override
   public int compareTo(Persona o) {
       final Persona p1 = o;
       return this.getNombre().compareTo(p1.getNombre());
   }
}


Sino implementas a Comparable, no podrías usar la linea 73 en el bean OrdenarPersonaPorNombre


rubn0x52.com KNOWLEDGE  SHOULD BE FREE!!!
If you don't have time to read, you don't have the time (or the tools) to write, Simple as that. Stephen

Beginner Web

Estoy muy confundida con tu codigo, tendre que leer mas  :o
7w7

rub'n

Cita de: Beginner Web en 14 Abril 2019, 07:25 AM
Estoy muy confundida con tu codigo, tendre que leer mas  :o

Pero en que? se siempre mas explicita, te comente un codigo que esta en el método ordenar.

por eso ahora veo que no es bueno editartelo mucho, pero recuerda que afuera, te econtraras tannntas maneras de hacer lo mismo, bueno eso si, unas mejores que otras XD


rubn0x52.com KNOWLEDGE  SHOULD BE FREE!!!
If you don't have time to read, you don't have the time (or the tools) to write, Simple as that. Stephen

Serapis

#6
Pongámoslo fácil, si al menos logras entenderlo, ya vale.

Tu tienes esto...
Código (java) [Seleccionar]

public void ordenar() {
   Persona cambio;
   boolean ordenado = true;
   while (ordenado == true) {
       ordenado = false;
       for (int i = 0; i < personas.size() - 1; i++) {
           if (personas.get(i).getNombre().compareTo(personas.get(i + 1).getNombre()) > 0) {
               cambio = personas.get(i);
               personas.set(i, personas.get(i + 1));
               personas.set(i + 1, cambio);
               ordenado = true;
           }
       }
   }
}



Modificando el mismo código... remplazo el bucle while por un for... y poco más...
Si simplemente quieres tirar de BubbleSort:
Código (java) [Seleccionar]

public void ordenar() {
   Persona cambio;        

   for (int j = 0; j < personas.size-2; j++){
       for (int i = 1; i < personas.size() - 1; i++){
           if (personas.get(i).getNombre().compareTo(personas.get(j).getNombre()) > 0){
               cambio = personas.get(j);
               personas.set(j, personas.get(i));  
               personas.set(i, cambio);                                                          
           }
       }              
   }
}



Este es el algoritmo Selectionsort, muy similar al BubbleSort, pero algo más rápido...
en cada ciclo interno, obtenemos siempre el mayor (si la comparación y el ordenamiento es de mayor a menor)  entre los que restan por ordenar... y se asigna al final de dicho bucle.
Es decir en el bucle interno se trata de encontrar el mayor

Código (java) [Seleccionar]

public void ordenar() {
   Persona cambio;
   Persona temp;

   for (int j = 0; j < personas.size-2; j++){
       temp = personas.get(j);
       for (int i = (j+1); i < personas.size() - 1; i++){
           if (personas.get(i).getNombre().compareTo(temp.getNombre()) > 0){
               cambio = personas.get(i);
               personas.set(i, temp);
               temp = cambio;                                            
           }
       }
       personas.set(j, temp);
   }
}


Por qué usar Selectionsort, en vez de Bubblesort? por 2 razones, el algoritmo es casi idéntico, ambos puedes escribirlos una y otra vez de cabeza en medio minuto... y porque bubbleSort, exige: n*n comparaciones (20x20)= 400 comparaciones, en tanto que Selectionsort exige algo menos de la la mitad: ((n-1 * n)\2) = (19*20)\2 = 190, dejo a tu investigación, porque Selectionsort, exije menos.

Se puede decir que bubblesort, es 'más tonto' que Selectionsort, su memoria es de pez, no 'recuerda' nada... Selectionsort, 'recuerda' al menos el menor/mayor que se va encontrando... tampoco es mucho más inteligente, exige solo 2 líneas más y cambiar el punto de inicio del bucle interno, a cambio es el doble de rápido (hace el trabajo con la mitad de comparaciones y de tiempo).

Se puede optimizar, evitando todos esos intercambios, a cambio necesitamos recordar el índice del ítem que se localiza como menor, para al final hacer un único intercambio, es decir la cantidad de intercambios se limita como mucho al número de ciclos del bucle externo. La optimización es inapreciable para cosas como 20-1000 elementos, cuando la cosa sube en magnitudes, 1, 10, 100 milllones es cuando se aprecia...

Código (java) [Seleccionar]

public void ordenar() {
   Persona temp;
   int k;

   for (int j = 0; j < personas.size-2; j++){
       k = j;                        
       for (int i = (j+1); i < personas.size() - 1; i++){
           if (personas.get(i).getNombre().compareTo(personas.get(k).getNombre()) > 0){
               k = i;
           }
       }
       temp = personas.get(k);  
       personas.set(k, personas.get(j));
       personas.set(j, temp);
   }
}


Modificado, para eliminar la indentación innecesaria (resultante del copy/paste/modifica)...

CalgaryCorpus

Opcion a lo mencionado previamente: Usar lambdas para implementar el comparator

Código (java) [Seleccionar]

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;

public class Persona {
     String nombre;
     int edad;
     
     public Persona(String nombre, int edad) {
         this.nombre = nombre;
         this.edad = edad;
     }
     
     public static void ordenaLista(List<Persona> l, String titulo,
                                    Comparator<Persona> comp) {
         Collections.sort(l, comp);
         System.out.println(titulo);
         for(Persona p: l) {
             System.out.println(p.nombre + " " + p.edad);
         }
     }
     
     public static void main(String []args){
         ArrayList<Persona> l = new ArrayList<>();
         l.add(new Persona("A", 30));
         l.add(new Persona("B", 29));
         l.add(new Persona("C", 28));
         l.add(new Persona("D", 27));

         ordenaLista(l, "Por nombre", (p1, p2) -> p1.nombre.compareTo(p2.nombre));
         ordenaLista(l, "Por edad", (p1, p2) -> (p1.edad - p2.edad));
     }
}


Aqui mi perfil en LinkedIn, invitame un cafe aqui