Como fazer a classificação corretamente em Java

Analisando o código-fonte de muitos projetos Java de código aberto, descobri que a maioria dos desenvolvedores implementa a classificação apenas de duas maneiras diferentes. Um deles é baseado no uso do método sort()de classe Collectionsou Arrays, e o outro é baseado no uso de estruturas de dados autoclassificadas, como TreeMape TreeSet.

Usando o método sort()

Se você precisar classificar uma coleção, use o arquivo Collections.sort().

// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

Se você precisar classificar um array, use o método Arrays.sort().

// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

O método sort()é muito conveniente quando a coleção ou array já está preenchida com valores.

Usando estruturas de dados de autoclassificação

Se você precisar classificar uma lista ( List) ou um conjunto ( Set), use uma TreeSetestrutura de classificação.

// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);

Se você precisar classificar um dicionário ( Map), use uma TreeMapestrutura de classificação. TreeMapordenado pela chave ( key).

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);

A abordagem acima é muito útil nos casos em que você precisa realizar um grande número de pesquisas por elementos de uma coleção. Estruturas de dados de autoclassificação têm uma eficiência O(log(n))melhor que O(n). Isso significa que quando a quantidade de dados na coleção dobra, o tempo de busca não dobra, mas aumenta em uma quantidade constante .

Abordagem ruim para classificar o problema

Você ainda pode encontrar exemplos em que os programadores descrevem algoritmos de classificação de forma independente. Considere o código de classificação apresentado abaixo (classificação de um array duplo em ordem crescente ). Este código não é apenas ineficiente, mas também ilegível. E há muitos exemplos desse tipo.

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}