Arrays de char
Pra começar, um exemplo simples demonstrando como ordenar os caracteres que compõe uma String:
String content = "ebdca"; char[] chars = content.toCharArray(); Arrays.sort(chars); String sorted = new String(chars); System.out.println(sorted); //abcde
A classe Arrays do Java ordena o array chars na ordem natural, alfabética. Mas o que acontece dentro do método sort? Como o array é pequeno o algoritmo utilizado para ordenação é o Insertion Sort, aonde a comparação ocorre no sentido de elementos da esquerda para a direita, garantindo que todos os elementos à esquerda estejam ordenados.
Simulação:
Array original -> e b d c a
Comparação 1 -> b < e, sim -> Resultado: b e d c a
Comparação 2 -> d < e, sim -> Resultado: b d e c a
Comparação 3 -> d < b, não
Comparação 4 -> c < e, sim -> Resultado: b d c e a
Comparação 5 -> c < d, sim -> Resultado: b c d e a
Comparação 6 -> c < b, não
...
A análise matemática de Insertion Sort varia de acordo com o conteúdo do array. No melhor caso, quando o array já está ordenado, o número de comparações seria linear O(n). Enquanto no pior caso, se os elementos estiverem em ordem decrescente, o número de comparações seria quadrático O( N^2). Em arrays pequenos Insertion Sort é uma ótima opção.
Em um array maior, com mais de 47 caracteres, o algoritmo utilizado é o QuickSort c/ Dual-Pivot. Como o nome diz, trata-se de uma variação de QuickSort com dois pivôs, abordagem parecida com QuickSort 3-way. Alguns estudos apontam que essa estratégia pode reduzir em até 10% o tempo em relação ao QuickSort tradicional. O algoritmo é recente, reformulado em 2009 por Vladimir Yaroslavskiy. O uso desses algoritmos fazem parte de melhorias do Java 7, verifique a classe DualPivotQuicksort.java.
Um detalhe muito importante sobre a comparação de char, é que o Java utiliza o Unicode para determinar a pontução de cada caracter. Nesse caso 'A' vem bem antes de 'a', e 'ã' vai bem depois de 'a'. Modificando o conteúdo da variável content para "abcdeãA", o valor de sorted seria "Aabcdeã". Volto a falar sobre isso no decorrer do post.
Array de String
O próximo trecho de código também é bem simples, nele coloco quatro strings em um array e peço para a classes Arrays realizar a ordenação:
String content[] = { "Jose", "Andre", "Claudia", "Bruna" };
Arrays.sort(content);
for (String s: content) {
System.out.print(s+" ");
}
Por se tratar de um array pequeno, a API do Java utiliza o Binary Insertion Sort, uma alternativa um pouco mais performática que usa a busca binária (binary search) para determinar a posição correta da troca. No pior caso o número de comparações é linearítmica O(n log n).
Já em arrays maiores, a partir de 32 elementos, o algoritmo de ordenação é o TimSort. TimSort é um algoritmo derivado de Merge Sort e Insertion Sort, no melhor caso o número de comparações é linear O(n), no pior é linearítmico O(n log n). Esse também é um algoritmo recente, descoberto em 2002 por Tim Peters, para a linguagem Python. O uso desses algoritmos também fazem parte de melhorias do Java 7, verifique a classes TimSort.java e ComparableTimSort.java.
Importante a ressalva de quem define a classificação de cada objeto durante o sort é o método compareTo de Comparable.
Collection<String> content = new TreeSet<>();
content.add("Jose");
content.add("Andre");
content.add("Claudia");
content.add("Bruna");
O TreeSet mantém os elementos classificados via Comparator ou Comparable, nesse caso através do método compareTo de Comparable. O TreeSet, como em versões anteriores do Java, mantém os elementos em TreeMap, que por sua vez continua utilizando o Red-Black Tree como algoritmo de ordenação. Por manter os elementos em uma ãrvore balanceada, esse algoritmo é extremamente eficiente, suas as operações são logaritmicas O(log n).
O trecho a seguir, um exemplo de ordenação em uma lista de String:
List<String> content = new ArrayList<>();
content.add("Jose");
content.add("Andre");
content.add("Claudia");
content.add("Bruna");
Collections.sort(content);
Em listas o Java usa o mesmo mecanismo de ordenação aplicado em arrays. O método sort de Collections usa o toArray da lista p/ recuperar os elementos contidos em um array, realiza a ordenação do array (Arrays.sort) e por fim atualiza os elementos na lista de acordo com resultado da ordenação.
O compareTo não funciona como o esperado?
A classificação natural da String é a ordem alfabética (lexicographically), ela ocorre através do método compareTo de Comparable. Esse método funciona perfeitamente quando não há necessidade de usar caracteres especiais, ou diferenciar letras minúsculas e maiúsculas. No começo do post, citei algumas dificuldades com o uso de caracteres com acentuação e maiúsculas com char, o mesmo vale para a String!
Veja um exemplo:
String content[] = { "Andrei", "Andréa", "Cláudia", "Claudio" };
Arrays.sort(content);
O resultado desse sort é: "Andrei", "Andréa", "Claudio" e "Cláudia".
Uma solução simples para esse tipo de problema é usar classe Collator, introduzida a partir do Java 5. Collator é uma classe abstrata, que implementa Comparator e define um conjunto de regras para realizar a comparação entre strings a partir de um determinado locale. Os principais idiomas são suportados por Collator, através de sua classe filha RuleBasedCollator. Uma sobrecarga do método sort, de Arrays, recebe um Comparator como argumento viabilizando o uso de Collator.
Veja:
Veja:
String content[] = { "Andrei", "andréa", "Cláudia", "Claudio" };
Collator colPtBr = Collator.getInstance(new Locale("pt_BR"));
Arrays.sort(content, colPtBr);
Note o valor "andréa", usando somente letras minúsculas. Agora o resultado do sort é: "andréa", "Andrei", "Cláudia" e "Claudio".
O Collator em pt_BR determina que caso duas palavras sejam semelhantes, variando apenas a acentuação, a palavra com acento vem logo após a palavra sem acento. Veja o resultado de comparações via Collator e Comparable com algumas Strings:
System.out.println(colPtBr.compare("Andréa", "andrea")); // 1: Andréa após andrea
System.out.println("Andréa".compareTo("andrea")); // -32: Andréa antes andrea
System.out.println(colPtBr.compare("maca", "maçã")); // -1: maca antes de maçã
System.out.println("maca".compareTo("maçã")); // -132: maca antes de maçã
Mais um detalhe sobre o Collator pt_BR, é em relação a letras minúsculas e maiúsculas. No caso de duas strings semelhantes, variando apenas letras minúsculas e maiúsculas, o Collator assume que a String com letra minúscula fica antes da String com maiúscula. Veja:
System.out.println(colPtBr.compare("pedro", "PEDRO")); // -1: pedro antes de PEDRO
System.out.println("pedro".compareTo("PEDRO")); // 32: pedro após PEDRO
A classe Collator permite o uso de estragégias "mais fortes" de comparação. No método setStrength é possível, por exemplo, pedir ao Collator que as diferenças entre acentuação, maiúsculas e minúsculas sejam ignoradas. Veja um exemplo:
colPtBr.setStrength(Collator.PRIMARY);
System.out.println(colPtBr.compare("pedro", "PEDRO")); // 0
System.out.println(colPtBr.compare("Andréa", "andrea")); // 0
System.out.println(colPtBr.compare("maca", "maçã")); // 0
Em casos mais simples, cuja a ordenação deve apenas desconsiderar diferenças entre letras maísculas e minúsculas, é possível usar um Comparator pronto e disponível na classe String: a constante CASE_INSENSITIVE_ORDER.
String content[] = { "A", "x", "c", "B", "d", "a" };
Arrays.sort(content, String.CASE_INSENSITIVE_ORDER);
Resultado da ordenação é: A a B c d x
Collator vs performance
O uso em de Collator em grande volume de objetos pode degradar a performance. Uma alternativa para reverter esse problema é utilizar a classe CollationKey, que armazena a chave binária em representação a uma string. Veja como funcionaria essa estratégia:
String content[] = { "Andrei", "andréa", "Cláudia", "Claudio" };
CollationKey[] collKeys = new CollationKey[content.length];
Collator colPtBr = Collator.getInstance(new Locale("pt_BR"));
for (int i = 0; i < collKeys.length; i++) {
//guarda a chave da string
collKeys[i] = colPtBr.getCollationKey(content[i]);
}
Arrays.sort(collKeys); //ordeno as chaves do collator
for (int i=0; i < collKeys.length; i++) {
System.out.print(content[i]+" ");
}
O truque desse último trecho é colocar as chaves geradas pelo Collator em um array, ordenar esse array e por fim exibir o as strings de acordo com a ordem das chaves.
