Ir para o conteúdo

Ordenar Listas

Uma lista ligada, simples ou dupla, permite conter vários elementos numa ordem sequencial, tipicamente, dispostos pela ordem de introdução. Ordenar essa lista implica percorrer uma ou mais vezes a lista, para podermos determinar, segundo algum critério, a ordem pela qual pretendemos colocar os elementos.

A criação de lógica de ordenação dos elementos irá seguir um qualquer algoritmo de ordenação, seja um quick sort, um bubble sort, ou outro qualquer de entre os inúmeros algoritmos que existem, e isso implicará criar código que até pode já estar implementando. Não seria mais simples dizer apenas qual o critério de comparação que queremos usar e pedir ao Java para nos ordenar a lista?

Embora não seja uma característica da linguagem, é uma característica da plataforma, disponível através de uma classe bastante útil no que toca a manipulação de estruturada de dados, não apenas listas. Essa classe é a java.util.Collections e é a classe que vamos usar para ordenar elementos sem termos de implementar um algoritmo ordenação.

Neste tutorial iremos criar uma pequena aplicação para ordenar listas de pessoas, consideramos apenas 3 critérios de ordem, mas muitos mais podiam ser implementados. Os exemplos completos encontram-se no fim da página.

Como base para o nosso exemplo, vamos considerar a classe Pessoa, apresentada no código abaixo1:

package org.pap.wiki.ordenarlistas;

import java.util.GregorianCalendar;

public class Pessoa implements Comparable {

    private GregorianCalendar birthdate;
    private String name;

    public Pessoa(String name, GregorianCalendar birthdate) {
        this.birthdate = birthdate;
        this.name = name;
    }

    public Pessoa(String name) {
        this(name, null);
    }

    public int getAge() {
        if(birthdate != null) {
        return new GregorianCalendar().get(GregorianCalendar.YEAR) -
                birthdate.get(GregorianCalendar.YEAR);
        }

        return 0;
    }

    public GregorianCalendar getBirthdate() {
        return birthdate;
    }

    public void setBirthdate(GregorianCalendar birthdate) {
        this.birthdate = birthdate;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }

        if (this == obj) {
            return true;
        }

        if (!(obj instanceof Pessoa)) {
            return false;
        }

        return name.equals(((Pessoa) obj).name);
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 29 * hash + (this.birthdate != null ? this.birthdate.hashCode() : 0);
        hash = 29 * hash + (this.name != null ? this.name.hashCode() : 0);
        return hash;
    }

    @Override
    public String toString() {
        return name;
    }
}

Classe Collections

Esta é uma classe que agrupa vários métodos de manipulação de estruturas de dados. Contém métodos para pesquisa binária, criação de estruturas sincronizadas, e especificamente, dois métodos para ordenação de listas, o método sort(List) e o método sort(List, Comparator).

Com estes dois métodos podemos ordenar qualquer estrutura que implemente a interface List, tendo apenas que criar o critério de comparação cuja implementação dependerá do objectivo e tipo de ordem que pretendemos.

Interface Comparable

A interface Comparable é usada quando pretendemos criar o critério de ordem natural.

Critério de ordem natural, ou ordenação natural, é o critério implementado pelos próprios objectos, e tipicamente implementa uma ordem que se considera ser a ordem natural dos objectos, aquela em que facilmente pensamos quando queremos ordenar determinado conjunto de objectos, por exemplo, quando pensamos em pessoas, é normal que as ordenemos pelo nome, se pensarmos em copos, talvez a sua capacidade seja a forma mais natural de os organizar.

A ordem natural não é imposta por definição nenhuma, podemos apenas dizer que, quando existe um método de ordenação no objecto, esse método fornece a ordem natural do objecto.

Ao implementarmos a interface Comparable somos forcados a implementar o método com a assinatura int compareTo(Object), é este o método especial que indica a ordem natural do elemento, e neste método criamos o critério de comparação a usar.

O método deve retornar um inteiro que exprima a relação entre o objecto passado como parâmetro e o objecto no qual é invocado o método. Essa relação deve ser expressa de forma a que seja retornado zero quando os objectos são iguais, um valor menor que zero quando o objecto passado é maior que o objecto de invocação e maior que zero em caso contrário.

O valor exacto retornado não é relevante2, e nunca devemos criar implementações onde esse valor tenha algum significado importante.

Vamos então, implementar a interface Comparable na nossa classe Pessoa, e definir o critério de comparação. Como critério natural vamos considerar a ordem alfabética, pelo que podemos recorrer à comparação natural já disponível na classe String3

public int compareTo(Object o) {
    //a comparação natural deve sempre lançar esta excepção e nunca deve tratar o elemento null
    if (o == null) {
        throw new NullPointerException();
    }

    Pessoa obj = (Pessoa) o;
    return name.compareTo(obj.name);
}

Para ordenarmos uma lista, usando a classe Collections, e considerando uma lista ligada com elementos Pessoa, chamada pessoas, teremos simplesmente fazer o seguinte:

Collections.sort(pessoas);

A nossa lista passará a estar ordenada.

Esta é também uma interface usada em várias classes da plataforma Java, sendo necessária em Hashtables, Hashmaps e outras estruturas que usam chaves na identificação de elementos. É assim uma interface que poderá ser considerada fundamental para quase todos os objectos que poderemos criar.

Interface Comparator

O problema da interface Comparable é que nos permite apenas um critério de comparação, não sendo assim possível, usando esta interface, implementar vários tipos de comparações e ordens. No entanto, isso não deve ser visto como uma limitação, uma vez que tal comportamento é premeditado e o Java oferece-nos outros mecanismos para lidar com situações onde precisemos de mais que uma forma de ordenar os elementos.

Chegamos então à interface Comparator. Com esta interface podemos criar várias classes que irão definir os critérios que precisamos para ordenar uma pessoa por, por exemplo, a sua data de nascimento, ou até, a sua idade.

Ao contrário do que fizemos para a classe Comparable, não serão os objectos Pessoa a conter o critério de implementação, mas sim classes auxiliares4 que serão depois passadas como parâmetro aos métodos de comparação.

Para implementar os critérios de comparação vamos então criar as classes necessárias, a primeira para comparar por idade, a segunda para comparar por data de nascimento:

package org.pap.wiki.ordenarlistas;

import java.util.Comparator;

public class AgeComparator implements Comparator<Pessoa> {

    public int compare(Pessoa o1, Pessoa o2) {
        return o1.getAge() - o2.getAge();
    }
}

package org.pap.wiki.ordenarlistas;

import java.util.Comparator;
import java.util.GregorianCalendar;

public class BirthdateComparator implements Comparator<Pessoa> {

    public int compare(Pessoa o1, Pessoa o2) {
        GregorianCalendar d1 = o1.getBirthdate();
        GregorianCalendar d2 = o2.getBirthdate();

        if(d1 == null || d2 == null ) {
            throw new NullPointerException();
        }

        return d1.compareTo(d2);
    }
}

Tal como fizemos anteriormente, vamos recorrer à classe Collections para ordenarmos a lista:

Collections.sort(pessoas, new AgeComparator());
//ou
Collections.sort(pessoas, new BirthdateComparator());

Reparem que passamos uma instância do critério de comparação que pretendemos usar, mas tal como no exemplo anterior, depois do código executado, a nossa lista está ordenada.

Conclusão

Os métodos sort apresentados são dois métodos úteis que permitem ordenar uma lista de forma simples, a implementação e critérios de ordem não exige muito código, sendo quase sempre conseguida através do uso do método compareTo disponível nas classes base da plataforma Java, e os métodos são bastante eficientes no que toca a ordenar estruturas, talvez mais que qualquer algoritmo implementado no mesmo tempo que demora a implementar os critérios de comparação, seja usando a interface Comparable, seja com a interface Comparator.

A exposição foi simples e focada apenas na implementação de critérios de comparação, e não existe muito mais a dizer no que toca a ordenar listas usando a classe Collections, como podem ver, o processo é bastante simples e evita a criação de algoritmos de ordenação quando o foco do nosso desenvolvimento não está nesses algoritmos.

Para referência, os métodos sort ordenam a lista de acordo com a ordem ascendente indicada no critério de comparação. A implementação segue uma modificação do algoritmo mergesort, oferecendo a garantia de ser estável, onde a posição de elementos iguais não é alterada, e de oferecer um custo \(O(N log(N))\) constante.

  1. Os comentários foram suprimidos para tornar a listagem mais curta. ↩

  2. Exceptua-se o valor zero, pela razão indicada acima ↩

  3. A grande maioria das classes do núcleo da plataforma Java implementa o método de comparação natural. ↩

  4. É possível que sejam os próprios elementos a implementar a interface, no entanto, essa opção poderá não ser viável porque é sempre necessário instanciar a classe para a poder usar. ↩