ordenar palavras

This message was edited 4 times. Last update was at 21/08/2011 19:57:26

Você só precisa escrever uma função que, dada duas Strings, diga se uma é maior, menor ou igual a outra.

Por exemplo vamos supor que, ao invés de ordenar uma sequencia por ordem alfabética, você queira ordenar pelo tamanho das palavras. O comparador seria implementado assim:

Então, seria fácil ordenar esse array:

Para uma ordenação lexicográfica, como vc quer, eu faria assim:
1. Todo char é implementado como um número, sendo o A maiusculo o 65. Portanto 'A'-65 = 0;
2. Portanto, é possível montar um array de inteiros, contendo a posição das letras na ordem que você deseja. Vamos supor, que seu alfabeto seja A, B, C, D, e você queria na ordem B, A, D, C. Esse array seria:

3. Para cada letra i, nas duas palavras:
1. Obtém-se o índice da i-ésima letra através da formula:
índice = Código ascii da letra - 65
2. Compara-se o valor ordem[i] de cada palavra. Se o valor da primeira palavra for < que o da segunda, retorna-se -1. Se o da segunda for maior que o da primeira, retorna-se 1. Caso contrário, adicione um ao i e prossiga para a próxima letra.

Se todas as letras forem iguais:
3. Retorna-se -1 caso a palavra 1 seja menor que a palavra 2, retorna-se 1 caso a palavra 2 seja menor que a palavra 1, ou 0 se forem iguais.

Vamos supor as palavras CADA e CACACA
1ª letra: Palavra 1: Índice de C = 67 - 65 = 2. Palavra 2: Índice de C = 67 - 65 = 2.
Como ordem[2] == ordem[2] == 4, então, continua-se o algorítmo

2ª letra: Palavra 1: Índice de A = 65 - 65 = 0. Palavra 2: Índice de A = 65 - 65 = 0.
Como ordem[0] == ordem[0] == 2, então, continua-se o algorítmo

3ª letra: Palavra 1: Índice de D = 68 - 65 = 3. Palavra 2: Índice de C = 67 - 65 = 2.
Como ordem[3] = 3 e ordem[2] = 4, logo palavra 1 < palavra 2. Portanto, o algorítmo retorna -1.

(Note que acamos que indicar que o "D" precede o "C", como queríamos).

Isso me lembra um exercício do google que discuti com o Mark há alguns dias atrás.

PS: Caso você trabalhe com Unicode, pode ser interessante definir a tabela de ordem num Map<Character, Integer>, ao invés de um array de primitivos. Assim, o próprio char poderia ser a entrada do map:

A mesma tabela de ordem ficaria:

E isso também evitaria calculos, por exemplo:

Java Ninja Membro desde: 10/06/2008 08:37:36 Mensagens: 284 Offline

Com Map eu já consegui ordenando só pela primeira letra da palavra, mas como já te disse quero ordenar por todas as letras da palavra na sequencia que eu defini e não consigo enxergar isso. :p

Releia o meu post. Eu descrevi detalhadamente um algorítmo que considera cada uma das letras da palavra, e ainda postei um exemplo de como vc deve fazer a comparação...

This message was edited 5 times. Last update was at 21/08/2011 20:36:46

Segue um exemplo do algorítmo implementado:

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class OrdemAlien {
	public static void main(String[] args) {
		String[] palavras = {"babaca", "bebada", "aebeo", "feio", "eba", "ebada", "agoda", "agoudo", "hoda", "foca", "faca", "fuca", "facada"};
		Arrays.sort(palavras, new AlienComparator());
		for (String palavra : palavras)
			System.out.println(palavra);
	}
}

//Considera um alfabeto formado pelas letras u,i,o,e,h,b,c,d,f,g,a - nesta ordem.
class AlienComparator implements Comparator<String>
{
	private Map<Character, Integer> ordem = new HashMap<Character, Integer>();
	
	public AlienComparator() {
		ordem.put('U', 1);
		ordem.put('I', 2);
		ordem.put('O', 3);
		ordem.put('E', 4);
		ordem.put('H', 5);
		ordem.put('B', 6);
		ordem.put('C', 7);
		ordem.put('D', 8);
		ordem.put('F', 9);
		ordem.put('G', 10);		
		ordem.put('A', 11);
	}
	
	@Override
	public int compare(String o1, String o2) {
		String str1 = o1.toUpperCase();
		String str2 = o2.toUpperCase();
		for (int i = 0; i < Math.min(o1.length(), o2.length()); i++)
		{			
			int ordem1 = ordem.get(str1.charAt(i));
			int ordem2 = ordem.get(str2.charAt(i));
			if (ordem1 != ordem2)
				return ordem1 - ordem2;
		}
		return o1.length() - o2.length();
	}
}

Se quiser definir uma nova ordem para as letras, simplesmente altere o map.

Java Ninja Membro desde: 10/06/2008 08:37:36 Mensagens: 284 Offline

Muito obrigado Vini, pois é exatamente por causa da provinha do Developer's day do Google que eu estou tentando implementar este algoritmo.

Algebra wrote:Muito obrigado Vini, pois é exatamente por causa da provinha do Developer's day do Google que eu estou tentando implementar este algoritmo.

Pois é, mas adianta receber a resposta pronta do GUJ?

Java Ninja Membro desde: 10/06/2008 08:37:36 Mensagens: 284 Offline

Eu já fiz a prova há alguns dias atrás porém, esta questão eu não consegui resolver e agora não quero permanecer na ignorância, quero entender como se faz mesmo com ajuda de alguém, afinal é para isso que servem os fóruns né!

Muito obrigado pela ajuda.

Abraços.

This message was edited 2 times. Last update was at 21/08/2011 20:45:37

No caso do Developers Day, ele pedia também para descartar as duplicatas. Isso é bem fácil, simplesmente use um TreeSet:

Note que o set também ordena.

Notícias, artigos e o maior fórum brasileiro sobre Java