Para uma tarefa da faculdade, necessito adaptar o algoritmo quicksort para um objeto "time", que contém dezenas de atributos, como estádio, nome, apelido, data de fundaao, etcs. Dentro da main, uma lista de arquivos htmls será recebida, com uma flag de terminação. A inserção na lista duplamente encadeada funciona perfeitamente, debuguei pelo Intellij.
A lista encadeada funciona por um objeto CelulaDupla, com referencias para frente, trás e o elemento TimeListaDuplaQuicksort
, que é o objeto contendo o time e seus atributos. A chave de ordenação do quicksort é a ordem alfabética do atributo apelido
, contido nos objetos da classe principal.
O grande problema está na função de quicksort. Adaptei o modelo que eu utilizava para arrays, com a função recursiva e uma função de swap, porém ela chama a si mesma infinitamente, com esq = 0 e dir = 28, logo na primeira chamada recursiva.
Já tentei debugar várias vezes, porém as 3 funções principais que estou utilizando aparentam estar funcionando de acordo com o esperado. Irei colocá-las abaixo, pois não sei em qual das 3 o problema está.
Função de retornar o elemento em pos:
/**
* Retorna o elemento na pos x, sem alterar a lista dupla
* @param pos int posicao do elemento a ser retornado
*/
public CelulaDupla elementoNaPosicao(int pos) throws Exception{
CelulaDupla resp;
int tamanho = tamanho();
if(pos < 0 || pos >= tamanho)
throw new Exception("Erro ao remover (posicao " + pos + " / " + tamanho + " invalida!");
// Caminhar ate a posicao anterior a desejada
CelulaDupla i = primeiro.prox;
for(int j = 0; j < pos; j++, i = i.prox);
resp = i;
return resp;
}
Função de swappar dois elementos
public void swap(int pos1, int pos2) throws Exception{
TimeListaDuplaQuicksort tmp = elementoNaPosicao(pos1).elemento;
elementoNaPosicao(pos1).elemento = elementoNaPosicao(pos2).elemento;
elementoNaPosicao(pos2).elemento = tmp;
}
Função do quicksort propriamente dito
/**
* Versão recursiva do quicksort, a ser chamado por uma funcao sobrecarregada acima, sem parâmeteos
* @param esq = limite na esquerda do quicksort
* @param dir = limite na direita do quicksort
* @return número de comparações entre apelidos dos times realizadas
* @throws Exception com problemas no getApelido(), que não devem ocorrer de forma alguma.
*/
public int quicksort(int esq, int dir) throws Exception{
int comparacoes = 0;
int i = esq, j = dir;
System.out.printf("Posicao atual de esq e dir: %d e %d.\n", esq, dir);
CelulaDupla pivo = primeiro;
//movimentar o pivo pra mediana
for(int k = 0; k < (dir+esq)/2 && pivo.prox != null; pivo = pivo.prox);
while (i <= j) {
// os dois fors abaixo são a versao lista dupla de "while (array[j] > pivo) j--;"
for(CelulaDupla tmp = this.elementoNaPosicao(i); tmp.elemento.getApelido().compareTo(pivo.elemento.getApelido()) < 0; tmp = tmp.prox, i = i+1, comparacoes++);
for(CelulaDupla tmp = this.elementoNaPosicao(j); tmp.elemento.getApelido().compareTo(pivo.elemento.getApelido()) > 0; tmp = tmp.ant, j = j-1, comparacoes++);
// add as duas comparacoes nao contabilizadas
comparacoes += 2;
if (i <= j) {
System.out.println("Swappando i e j, nas posicoes "+i + " "+j);
swap(i, j);
i++;
j--;
}
}
//chamadas recursivas
if (esq < j)
comparacoes += quicksort(esq, j);
if (i < dir)
comparacoes += quicksort(i, dir);
return comparacoes;
}