[SOLUCIONADO] Ordenar ArrayList

[shenron66]

Hola

Este es mi primer post, me pueden ayudar.

Como puedo hacer para ordenar un ArrayList de contraseñas siguiendo este orden:

- 1º las letras siguiendo el orden del alfabeto español,
- 2º los números del 0 al 9
- 3º símbolos especiales ordenados por su código en Unicode UTF-16 que es el orden utilizado en java internamente, menos el espacio en blanco.

Por ejemplo:

ArrayList con [password1, password2, pass, pass2,pass%,pass$]

Y la salida es:
pass password1 password2 pass2 pass$ pass%


Gracias por la ayuda.

[Xerelo]

Teniendo en cuenta que esa List será de String, lo mejor que puedes hacer es crear un Comparator y llamar al método Collections.sort(List,Comparator)

http://docs.oracle.com/javase/6/docs...java.util.List, java.util.Comparator)

http://javaparanulos.blogspot.com.es...r-en-java.html

[shenron66]

Iniciado por Xerelo

Teniendo en cuenta que esa List será de String, lo mejor que puedes hacer es crear un Comparator y llamar al método Collections.sort(List,Comparator)

[url]http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List[/url], java.util.Comparator)

[url]http://javaparanulos.blogspot.com.es/2012/02/comparator-en-java.html[/url]

Gracias lo estube mirando pero no me sirve, porque el valor de los numeros es mas pequeño que el de las letras y no los ordena como quiero.

Saludos.

[Andreslrz]

Pues segun veo lo que debes hacer es primero separar la contraseña por caracteres y determinar como piensas ordenar, ya que si una contraseña empieza con una letra y otra con un caracter especial no puedes comparar el ascii con el UTF-16, en ese caso deberias escoger que iria primero, si el caracter especial o la letra o un numero.

Ya despues que escojas eso, es facil, solo escoges por orden de tipo de caracter para agrupar y ordenas con un algoritmo de ordenamiento, puede ser un bubble sort o un merge sort, despues repites lo mismo para los caracteres en la segunda posicion y asi sucesivamente, no tengo un algoritmo claro pero doy almenos la idea general.

[HackmanC]

Hola,

Iniciado por Xerelo

Teniendo en cuenta que esa List será de String, lo mejor que puedes hacer es crear un Comparator y llamar al método Collections.sort(List,Comparator) ...

Iniciado por shenron66

Gracias lo estube mirando pero no me sirve, porque el valor de los numeros es mas pequeño que el de las letras y no los ordena como quiero. ...

Me imagino que a lo que se refiere Xerelo es que tienes que implementar la interface Comparator, que por defecto al ser una interface, no define la implementación. En otras palabras, cual va primero lo defines tú. Y tu tienes que implementar la lógica, no basarte en la implementación básica de String.compareTo().

Posiblemente estás confundiendo Collections.sort(List) con Collections.sort(List, Comparator). Averigua como funciona la interface Comparator realmente.

Iniciado por Andreslrz

Pues segun veo lo que debes hacer es primero separar la contraseña por caracteres y determinar como piensas ordenar, ya que si una contraseña empieza con una letra y otra con un caracter especial no puedes comparar el ascii con el UTF-16, en ese caso deberias escoger que iria primero, si el caracter especial o la letra o un numero. ...

Técnicamente, usando la interface Comparator no importa, es decir, Java usa Unicode internamente y nunca hace conversiones a ASCII u otra tabla de caracteres sino se especifica explícitamente. Así que todos los números, letras y caracteres definidos dentro de ASCII están dentro de Unicode, y como bien sabes cada uno de dichos glifos tiene un número asignado, un 'code point'.

Si comparo el caracter Unicode \u0001 (un caracter de control) con \u0041 (una letra), simplemente va a decir que el mayor es la letra puesto que su número es mas grande.

Para cambiar eso hay que implementar una interface Comparator<T> de tipo String que pase por cada letra del String y compare su valor con cada letra del otro String, haciendo los ajustes necesarios en la implementación para que los números vayan después de las letras (que no es la implementación normal de String.compareTo()).

Iniciado por Andreslrz

Ya despues que escojas eso, es facil, solo escoges por orden de tipo de caracter para agrupar y ordenas con un algoritmo de ordenamiento, puede ser un bubble sort o un merge sort, despues repites lo mismo para los caracteres en la segunda posicion y asi sucesivamente, no tengo un algoritmo claro pero doy almenos la idea general.

El método estático sort() de la clase Collections tiene ya implementado el algoritmo más eficiente para ordenar cualquier colección. Lo único que tienes que hacer es insertarle la lógica de cual es mas grande y cual es mas pequeño con una interface Comparator.

Saludos,

[Profesor_Falken]

El método estático sort() de la clase Collections tiene ya implementado el algoritmo más eficiente para ordenar cualquier colección. Lo único que tienes que hacer es insertarle la lógica de cual es mas grande y cual es mas pequeño con una interface Comparator.

Solo por completar la excelente respuesta de HackmanC, comentar que el metodo sort de Java utiliza concretamente el algoritmo Dual-Pivot Quicksort de Vladimir Yaroslavskiy.

Aqui teneis la especificacion de dicho algoritmo:
http://iaroslavski.narod.ru/quicksor...tQuicksort.pdf

Dicho algoritmo se comporta muy bien en la mayoria de los casos (O(nLogn)) aunque siempre hay situaciones limite en las que otros metodos de ordenacion pueden ser algo mas rapidos (por ejemplo, si la lista ya esta ordenada).


Un saludo

[shenron66]

Gracias a todos por las respuestas

[shenron66]

Iniciado por HackmanC

Hola,

Para cambiar eso hay que implementar una interface Comparator<T> de tipo String que pase por cada letra del String y compare su valor con cada letra del otro String, haciendo los ajustes necesarios en la implementación para que los números vayan después de las letras (que no es la implementación normal de String.compareTo()).


El método estático sort() de la clase Collections tiene ya implementado el algoritmo más eficiente para ordenar cualquier colección. Lo único que tienes que hacer es insertarle la lógica de cual es mas grande y cual es mas pequeño con una interface Comparator.

Hola de nuevo

Estube mirando documentacion de comparator como en este enlace:

http://www.aprenderaprogramar.es/index.php?option=com_attachments&task=download&id= 541

Intente hacer el codigo pero no se como implementarlo:

http://pastebin.com/SV9cyB8K

Me pueden ayudar porfavor. Gracias

[Xerelo]

Primero compruebas qué contraseña tiene menor tamaño.

Haces un sólo bucle for hasta el número del tamaño del password menor (evitas outbounds)

Dentro de ese bucle, comparas la posición que marca el índice del for en los dos password. Si son iguales las letras (aquí dependerá de cómo consideres mayúsculas y minúsculas) continuas el bucle. Recuerda que String se compara con equals, no con ==

Si no son iguales, llamas a un método que compara dos letras, que te devuelve cual es mayor y te sales del bucle.

En el método de comparar:

Ver de qué tipo son las letras, si son de distinto tipo, ya sabes cuál es mayor.

Si coinciden, comparas el valor en char (no sé si para los símbolos especiales te vale) o el codepoint

[Profesor_Falken]

Es que hay que currase un poco el comparador.

Aqui te pongo uno sobre tu codigo. No lo he probado y lo mismo ni compila (lo he hecho en el notepad) pero te puede dar una idea

Código Java:

public class Prueba {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<String> lista = new ArrayList<>();
 
        //solo letras minusculas
        lista.add("12a");
        lista.add("acd");
        lista.add("a%c");
        lista.add("bdc");
        lista.add("bc");//las contrasenas no tienen que ser del mismo tamano
 
        Collections.sort(lista, new Ordenar());
 
        System.out.print(lista);
    }
}
 
class Ordenar implements Comparator<String> {
 
    @Override
    public int compare(String o1, String o2) {
        if (o1 == null && o2 == null) {
            return 0;
        } else if (o2 == null) {
            return -1;
        } else if (o1 == null) {
            return 1;
        }
        
        //Select shortest to pivot on
        int shortest = (o1.length() <= o2.length()) ? o1.length() : o2.length();
 
        for (int i = 0; i < shortest; i++) {
            char charO1 = o1.charAt(i);
            char charO2 = o2.charAt(i);
 
            if (Character.isLetter(charO1)) {
                if (!Character.isLetter(charO2)) {
                    return -1;
                } else {
                    int comp = Character.compare(charO1, charO2);
                    if (comp != 0) {
                        return comp;
                    }
                }
            } else if (Character.isDigit(charO1)) {
                if (Character.isLetter(charO2)) {
                    return 1;
                } else if (Character.isDigit(charO2)) {
                    int comp = Character.compare(charO1, charO2);
                    if (comp != 0) {
                        return comp;
                    }
                } else {
                    return -1;
                }
            } else {
                if (Character.isLetter(charO2) || Character.isDigit(charO2)) {
                    return 1;                    
                } else {
                    int comp = Character.compare(charO1, charO2);
                    if (comp != 0) {
                        return comp;
                    }
                }
            }
        }
 
        return (o1.length() <= o2.length()) ? -1 : 1;
    }
}
 

Un saludo

[shenron66]

Gracias a los dos.

Probe tu codigo Profesor_Falken y compila bien.
Lo entiendo poco y entiendo poco de esto porque soy novato

el codigo esta bien para:

password1,password2,pass,pass2

ya que la salida es : pass,password1,password2,pass2

pero creo que esta mal para: 12a, acd, a%c, bdc, bc
la salida es : acd, a%c, bc, bdc, 12a

Saludos y gracias

[shenron66]

Iniciado por shenron66

Gracias a los dos.

pero creo que esta mal para: 12a, acd, a%c, bdc, bc
la salida es : acd, a%c, bc, bdc, 12a

Saludos y gracias

Me confundi, esta bien para ese caso.

Voy a intentar entenderlo.

Muchas gracias Profesor_Falken , eres el amo de Java, algún día quiero ser como tu de bueno

[HackmanC]

Hola,

Iniciado por Profesor_Falken

Es que hay que currase un poco el comparador.

Ciertamente, y agregando mi versión del mismo, aunque no estoy seguro que de exactamente los mismo resultados, posiblemente sea mas simple de darle mantenimiento. Ahora solo queda observar el caso de la Ñ/ñ, CH/ch y otros casos especiales.

Código Java:

import java.util.Comparator;
 
public class Ordenar implements Comparator<String> {
 
    private int compare(char c1, char c2) {
        int i1 = Character.isLetter(c1) ? 2 : Character.isDigit(c1) ? 1 : 0;
        int i2 = Character.isLetter(c2) ? 2 : Character.isDigit(c2) ? 1 : 0;
 
        if (i1 != i2) {
            return i2 - i1;
        }
 
        return Character.compare(c1, c2);
    }
 
    @Override
    public int compare(String o1, String o2) {
        if (o2.length() != o1.length()) {
            return o1.length() - o2.length();
        }
 
        int length = o1.length();
        int compare;
        for (int i = 0; i < length; i++) {
            compare = compare(o1.charAt(i), o2.charAt(i));
            if (compare != 0) {
                return compare;
            }
        }
 
        return 0;
    }
 
}
 

Iniciado por Profesor_Falken

... comentar que el metodo sort de Java utiliza concretamente el algoritmo Dual-Pivot Quicksort de Vladimir Yaroslavskiy. ...

De eso no puedo estar completamente seguro, pero según la documentación de Oracle, usa el método 'merge sort' ligeramente optimizado. Lo único que sé es que es rápido y estable.

http://docs.oracle.com/javase/tutori...hms/index.html

Saludos,

[Profesor_Falken]

Buenas,

Está muy bien y es más DRY, solo le veo dos pegas de funcionamiento:
-Si un elemento de la lista es null explota con un NullPointerException.
-Da prioridad a las palabras con menos letras, que no es lo que se busca.

Por ejemplo, con la lista del ejemplo de este post devuelve esta ordenación:
[bc, acd, a%c, bdc, 12a]

Cuando debería devolver ésta:
acd, a%c, bc, bdc, 12a

Para arreglarlo basta con desplazar el if de la longitud después del bucle.

Código Java:

@Override
    public int compare(String o1, String o2) {
        int length = o1.length();
        int compare;
        for (int i = 0; i < length; i++) {
            compare = compare(o1.charAt(i), o2.charAt(i));
            if (compare != 0) {
                return compare;
            }
        }
       if (o2.length() != length) {
            return length - o2.length();
        }
 
        return 0;
    }
 

Un saludo

[HackmanC]

Hola,

Tienes toda la razón, solo un par de comentarios adicionales con el afán de compartir nada mas,

Iniciado por Profesor_Falken

...
-Si un elemento de la lista es null explota con un NullPointerException.

La especificación de Objects.compare(T o1, T o2, Comparator<T>), así lo define, si uno es null 'posiblemente' tire un NullPointerException. No digo que no se pueda corregir o no sea buena observación, simplemente que la interface Comparator no define eso.

Sería aconsejable validar los nulos al principio con el código que propusiste.

Iniciado por Profesor_Falken

...
-Da prioridad a las palabras con menos letras, que no es lo que se busca.

Tienes toda la razón en eso también, ya será cosa de shenron66 modificarlo a sus requerimientos correctamente, que adicionalmente indicaba que necesitaba el ordenamiento en Español, eso incluye la Ñ en la posición correcta, y no lo implementé tampoco. Solo es para que se dé una idea de como hacerlo.

Iniciado por Profesor_Falken

...
Para arreglarlo basta con desplazar el if de la longitud después del bucle.
...

Creo que la corrección sería mas compleja que eso, porque en el ciclo, si no son de la misma longitud posiblemente tiraría una excepción. Pero es muy buena observación y tendrá que modificarlo shenron66 consecuentemente.

Saludos,

[shenron66]

Gracias HackmanC y Profesor_Falken.

Este foro es genial, Salu2 .

[shenron66]

Hola

Solo una cosa mas Profesor_Falken como puedo implementar la ñ para que vaya despues de la n y antes de la o . Lo estube mirando y no hay forma de que me salga.

saludos

[Profesor_Falken]

Ya, y también tendrás el mismo problema con los acentos.

Utilizando una complementación de Collator (clase añadida con Java 5 y una de las grandes olvidadas de Java), puede realizar comparaciones de lenguaje natural fácilmente. Solo debes cambiar dos lineas.

1- Crear un collator utilizando el locale que nos interese, en este caso el español:
Collator collator = Collator.getInstance(new Locale("es", "ES"));


2- Luego cuando haces la comparacion de letras, puedes usar el collator para comparar. Collator trabaja con Strings, por lo que podemos hacer una conversion:
int comp = collator.compare(String.valueOf(charO1), String.valueOf(charO2));

Esto aplicaría tanto para el código que te puse como para el de HackmanC

Por ejemplo, partiendo de mi código inicial:

Código Java:

public class Prueba {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<String> lista = new ArrayList<>();
 
        //solo letras minusculas
        lista.add("12a");
        lista.add("acd");
        lista.add("and");
        lista.add("aod");        
        lista.add("a%c");        
        lista.add("a0d");
        lista.add("aád");
        lista.add("bdc");
        lista.add("añd");
        lista.add("bc"); //las contrasenas no tienen que ser del mismo tamano
 
        Collections.sort(lista, new Ordenar());
 
        System.out.print(lista);
    }
}
 
class Ordenar implements Comparator<String> {
 
    @Override
    public int compare(String o1, String o2) {
        if (o1 == null && o2 == null) {
            return 0;
        } else if (o2 == null) {
            return -1;
        } else if (o1 == null) {
            return 1;
        }
        Collator collator = Collator.getInstance(new Locale("es", "ES"));
 
        //Select shortest to pivot on
        int shortest = (o1.length() <= o2.length()) ? o1.length() : o2.length();
 
        for (int i = 0; i < shortest; i++) {
            char charO1 = o1.charAt(i);
            char charO2 = o2.charAt(i);
 
            if (Character.isLetter(charO1)) {
                if (!Character.isLetter(charO2)) {
                    return -1;
                } else {
                    int comp = collator.compare(String.valueOf(charO1), String.valueOf(charO2));
                    if (comp != 0) {
                        return comp;
                    }
                }
            } else if (Character.isDigit(charO1)) {
                if (Character.isLetter(charO2)) {
                    return 1;
                } else if (Character.isDigit(charO2)) {
                    int comp = collator.compare(charO1, charO2);
                    if (comp != 0) {
                        return comp;
                    }
                } else {
                    return -1;
                }
            } else {
                if (Character.isLetter(charO2) || Character.isDigit(charO2)) {
                    return 1;
                } else {
                    int comp = collator.compare(charO1, charO2);
                    if (comp != 0) {
                        return comp;
                    }
                }
            }
        }
 
        return (o1.length() <= o2.length()) ? -1 : 1;
    }
}
 

Resultado: [aád, acd, and, añd, aod, a0d, a%c, bc, bdc, 12a]

Un saludo