Bem, eu pensava que os termos
order e
sort em inglês significavam a mesma coisa, mas a gente já sabe que isso não é verdade. Vimos duas interfaces úteis para definir o modo como objetos devem ser ordenados numa coleção. E agora, como faço a ordenação, de fato?
Ordenando Coleções
Tome o seguinte trecho de código, onde tentamos ordenar uma certa lista de pessoas:
import java.util.*;
import java.io.*;
class Pessoa {
private String nome;
public Pessoa (String nome){
this.nome = nome;
}
public String getNome() {
return this.nome;
}
public void setNome(String nome){
this.nome = nome;
}
public String toString() {
String result = "nome: " + this.nome;
return result;
}
}
public class Principal {
public static void main(String[] args){
List<Pessoa> listaPessoa = new ArrayList<Pessoa>();
listaPessoa.add(new Pessoa("Fulano"));
listaPessoa.add(new Pessoa("Cicrano"));
listaPessoa.add(new Pessoa("Beltrano"));
Collections.sort(listaPessoa);
System.out.println(listaPessoa);
}
}
Note que não definimos qualquer ordenação natural, como no post anterior. Ao tentar compilar este código, temos o seguinte:
Se consultarmos a api do Java para este método, veremos que:
static <T extends Comparable<? super T>>
void sort(List<T> list)
É meio confuso ler esta assinatura de método, mas perceba que a lista que o método recebe é parametrizada. E o parâmetro é uma classe que deve implementar a interface Comparable. Mais precisamente, qualquer subclasse para qual exista uma superclasse que implemente esta interface.
Existe uma sobrecarga deste método, que recebe uma instância de Comparator:
static <T> void sort(List<T> list, Comparator<? super T> c)
Também vimos como definir um Comparator no post anterior. O mais interessante, é que podemos instanciar um Comparator e definir o método de comparação ai mesmo, na passagem de parâmetros, ao invés de se criar uma classe específica. Isto é recomendado apenas se esta instância de comparator, com este critério de ordenação, for utilizado somente uma vez:
Collections.sort(listaPessoa, new Comparator<Pessoa>() {
public int compare(Pessoa a, Pessoa b) {
return a.getNome().compareTo(b.getNome());
}
});
Existem coisas interessantes como definir uma ordem inversa à ordem natural, de maneira extremamente simples. Para isso, usa-se o método estático Collections.reverseOrder(), que retorna uma instância de Comparator. Este método deve ser usado se a sua classe implementa a interface Comparable. Caso este não seja o caso, e já exista uma implementação de Comparator, use Collections.reverseOrder(Comparator<T> cmp). Pense como se estes métodos retornassem o resultado dos métodos que já vimos anteriormente, multiplicados por -1.
Ordenando Arrays
Assim como vimos a classe utilitária Collections para a ordenação de coleções, existe também a classe utilitária Arrays, com os mesmos métodos de ordenação: o que espera listas cujo tipo parametrizado é uma instância de Comparable, e o que espera uma instância de Comparable como definição de ordenação. Em adição, existem diversos métodos sobrecarregados iguais a esses, contemplando cada tipo primitivo (char, byte, short, int, boolean, float, double - esqueci de algum?). E mais: para esta classe utilitária, em especial, existem métodos que nos permitem ordenar apenas uma parte do array de valores. Vale dar uma conferida rápida na api desta classe.
Buscas em Coleções
Um dos métodos mais eficientes e mais conhecidos para buscas é a pesquisa binária. A classe utilitária Collections possui um método chamado binarySearch, que contempla este tipo de pesquisa:
static <T> int
binarySearch(List<? extends Comparable<? super T>> list,
T key)
static <T> int
binarySearch(List<? extends T> list, T key,
Comparator<? super T> c)
Note que ambos os métodos esperam uma lista, pelos motivos que veremos logo a seguir.
Entretanto, é importante seguir algumas regras:
- Buscas com sucesso retornam o índice do elemento procurado na lista passada pro parâmetro (para que o objeto possa ser resgatado usando o método get(int index) da lista).
- Buscas sem sucesso retornam um valor negativo, que pode ser encarado cmo a posição de inserção do novo elemento da lista. Por ser um valor negativo (já que 0 é uma posição válida dentro da lista), a primeira posição de inserção válida é -1. Então, este número deve ser "transformado" para um valor positivo através do cálculo (-<ponto de inserção> - 1).
- A coleção deve ser ordenada antes de se efetuar qualquer busca.
- Se a coleção for ordenada utilizando determinado método de classificação (natural - implementando a interface Comparable - ou algum específico - implementando a interface Comparator), as buscas devem ser feitas utilizando exatamente o mesmo método de classificação.
O não uso da mesma estratégia de classificação na busca e na ordenação, ou a não ordenação da coleção antes da busca pode tornar os resultados da busca imprevisiveis.
Buscando em Arrays
Novamente, existem métodos similares aos citados para buscas nas coleções na classe utilitária Arrays. As regras para o uso destes métodos são as mesmas que as citadas para as coleções. Também existem sobrecargas desses métodos para cada primitiva existente, bem como sobrecargas para que buscas sejam efetuadas apenas numa parte do array. Para dúvidas, consultar a api.
Curiosidades sobre métodos de busca
A despeito do conhecimento da maioria, existe um tipo de busca chamado de Busca por Interpolação, que é mais eficiente que a busca binária. Isso porque o algoritmo utiliza interpolação linear para meio que "adivinhar" a posição do elemeto procurado, no caso de elementos uniformemente distribuídos. Vale a pena dar uma olhada, a título de informação.
Esta obra está licenciada sob uma Licença Creative Commons.
Postagens
