Ordenar listas ligadas

[Bartude]

Boas, eu queria ordenar uma lista ligada, só que ta a dar mal. A minha lista ligada chama-se atletas e é do tipo Atleta(uma instancia). La dentro tem os atributos ouro, prata e bronze. E queria ordenar primeiro por ouro, depois prata e depois bronze. O codigo seguinte é so o de ouro, depois é so alterar para os outros.

Atleta temp;
for (int i = 0; i < atletas.size() - 1; i++) {
		for (int j = i + 1; j < atletas.size() - 1; j++) {
			Atleta temp2 = atletas.get(j);
			if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
				temp = atletas.get(i);
				atletas.removesem(i);
				atletas.add(i, atletas.get(j));
				atletas.removesem(j);
				atletas.add(j, temp);
			}
		}
	}

O removesem é um metodo da classe lista ligada, que quando remove, em vez de retroceder todos os elementos, deixa ali um espaço em branco, pa depois inserir.

public int removesem(int index){
	assert(index >= 0 && index < size()); //force valid index
	temp = head; //start at the beginning of the list

	if(index == 0){
			head = null;
			counter--;
			return 0;

	}
	else if(index == size()){
			tail = null;
			counter--;
			return 0;
	}

	//iterate to the position before the index
	for(int i = 0; i < index; i++) temp = temp.next;

	//set temp.next to point to the Node next to the Node to be removed
	temp = null;
	counter--;
	return 0;
}

O problema é que a partir dum certo ponto, começa a inserir tudo igual, e acaba por ficar 3/4 da lista ligada igual.

Alguem sabe qual o problema? Brigado

[tiagotavares]

Boas,

1. Não usas a variavel temp2
   
2. Tu removes a posição i e tudo passa a estar 1 index atrás e pegas no j (depois de remover é j+1).
   
3. 3ª linha do if é: atletas.add(i, temp2); agora j já é j e nºao j+1 porque existe mais uma posição.
   

O que estás a fazer neste algoritmo é trocar o valor de i com j sempre que encontras 1 menor (corrigido nos 3 pontos acima) até chegares ao fim. (Esta linha é mais um aparte.

Penso que a maneira que expliquei e corrigi está correta mas posso me ter enganado.

Espero ter ajudado 😉

[Bartude]

Boas, isso dito assim, é um bocado confuso pa mim.

Pelo que eu percebi, o codigo atao vai ficar assim:

for (int i = 0; i < atletas.size() - 1; i++) {
	    for (int j = i + 1; j < atletas.size() - 1; j++) {
		    Atleta temp2 = atletas.get(j);
		    if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
			    temp = atletas.get(i);
			    atletas.removesem(i);
			    j++;
			    atletas.add(i, temp2);
			    atletas.removesem(j);
			    atletas.add(j, temp);
		    }
	    }
    }

É assim que deveria de tar?

[tiagotavares]

Creio que será sem o j++

for (int i = 0; i < atletas.size() - 1; i++) {
 for (int j = i + 1; j < atletas.size() - 1; j++) {
		Atleta temp2 = atletas.get(j);
		if (atletas.get(i).getOuro() < atletas.get(j).getOuro()) {
				temp = atletas.get(i);
				atletas.removesem(i);
				atletas.add(i, temp2);
				atletas.removesem(j);
				atletas.add(j, temp);
		  }
  }
}

Depois diz se funciona 😉

Edited June 20, 2012 at 10:24 AM by tiagotavares

[118]

não seria mais indicado criares uma nova lista e ires inserindo ordenado? Ou melhor, usar um comparator que é como normalmente se faz em java

[KiNgPiTo]

É obrigatório usar LinkedList? Se usares uma TreeSet com um comparator definido por ti, terás sempre a lista ordenada...