Núcleo de Ferrita

Cuando uno se decide a iniciarse en la programación, una de las primeras cosas "complicadas" que aprende es a ordenar listas y a hacer búsquedas en dichas listas, sobre todo en listas previamente ordenadas.

Todo ello es algo básico y fundamental que se debe aprender sí o sí. Sin embargo, a la hora de tener que ordenar una lista en una aplicación más compleja, lo normal es utilizar alguno de los métodos que pueda facilitar el lenguaje, y ya se sabe que Java nos ofrece una api muy completa con la que se puede hacer prácticamente de todo.

Lo que vamos a ver hoy es la clase de métodos estáticos Collections. Esta clase tiene métodos para ordenar listas, desordenarlas aleatoriamente, hacer búsquedas binarias, obtener el máximo/mínimo elemento, copiar elementos, invertirlos, frecuencia de un elemento... infinidad de posibilidades.

Evidentemente puede compararse/ordenarse/buscarse en listas de cualquier tipo de objeto, pero entonces, ¿como sabe Java que un elemento de la lista es "menor" que otro para poder ordenarlos?

Bien, la lista puede ser de dos tipos de clases:

• Clases que heredan de Comparable.
  
• Resto de clases.
  

Para conseguir ordenar la lista, la clase Collections hace uso del método compare, donde se especifica qué elemento es mayor o menor que otro. Cuando se utiliza una clase que extiende a Comparable (como por ejemplo Integer), intrínsicamente esa clase ya lleva implementado el método compare. Cuando se utiliza por ejemplo, una clase personalizada de las que podemos crear en nuestros programas, podemos utilizar la ayuda de un Comparator, al que le implementamos el método compare y que debemos facilitar a la hora de ordenar la lista.

Veámoslo con un ejemplo de ordenación, primero con una lista de enteros, y luego con una lista de otra clase. Para rellenar las listas utilizaremos números aleatorios con la ayuda de Random.

List<Integer> numbers = new ArrayList<Integer> ();
int n = 10; // número de elementos en la lista
int max = 100; // máximo elemento posible

// Creamos la semilla aleatoria.
Random random = new Random (System.currentTimeMillis());

while (numbers.size() < N) {
    // Integer extiende a Comparable
    numbers.add(new Integer (random.nextInt(max)));
}
  
System.out.println("Sin ordenar: " + numbers);
Collections.sort(numbers);
System.out.println("Ordenado...: " + numbers);

Este ejemplo visualizará la lista desordenada y luego ordenada de menor a mayor.

Imaginemos ahora que queremos ordenarla de mayor a menor. Una manera de hacerlo puede ser ayudarnos de la clase anteriormente mencionada Comparator, definiendo la ordenación de enteros a la inversa de como está por defecto. El método compare devuelve un número menor que cero si el primer elemento es menor que el segundo, mayor que cero si el primer elemento es mayor que el segundo, e igual a cero si ambos elementos son iguales.

Comparator<Integer> comparator = new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
        return b-a;
    }
};
// Ahora ordenamos utilizando el comparador  
Collections.sort(numbers, comparator);

Veamos otro ejemplo con una clase propia CustomPoint2D:

class CustomPoint2D {
    private int x;
    private int y;
 
    CustomPoint2D (int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    // ... getters, setters... 

    public String toString () {
        return "{" + x + ", " + y + "}";
    }
}

Podríamos ordenarlo definiendo por ejemplo, que un CustomPoint2D es menor que otro si la suma de sus puntos x e y es menor que la del segundo objeto.

List <CustomPoint2D> points = new ArrayList <CustomPoint2D> ();
while (points.size() < N) {
    points.add(new CustomPoint2D (random.nextInt(max), random.nextInt(max)));
}
  
Comparator <CustomPoint2D> comparatorPoint = new Comparator<CustomPoint2D> () {
    public int compare (CustomPoint2D p, CustomPoint2D q) {
        return (p.getX() + p.getY()) - (q.getX() + q.getY());
    }
};
  
System.out.println("Sin ordenar: " + points);
Collections.sort(points, comparatorPoint);
System.out.println("Ordenado...: " + points);

¿Alguna duda?

Agradecimientos por la idea y algún ejemplo para este post a mis compañeros Diego F. y Carlos A.