0
For a college task, I need to adapt the quicksort algorithm to a "time" object, which contains dozens of attributes such as stadium, name, nickname, date of foundation, etcs. Within main, a list of htmls files will be received, with a termination flag. Insertion in the double-chained list works perfectly, debugged by Intellij.
The chained list works by a Celluladupla object, with forward, back and element references TimeListaDuplaQuicksort
, which is the object containing the time and its attributes. The quicksort sorting key is the alphabetical order of the attribute apelido
, contained in the main class objects.
The big problem is in the quicksort function. I adapted the model I used to arrays, with the recursive function and a swap function, but she calls herself infinitely, with Esq = 0 and dir = 28, right at the first recursive call.
I have tried debugging several times, but the 3 main functions I am using appear to be working as expected. I’ll put them down, 'cause I don’t know which of the three the problem is.
Function of returning the element in 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;
}
Two element swap function
public void swap(int pos1, int pos2) throws Exception{
TimeListaDuplaQuicksort tmp = elementoNaPosicao(pos1).elemento;
elementoNaPosicao(pos1).elemento = elementoNaPosicao(pos2).elemento;
elementoNaPosicao(pos2).elemento = tmp;
}
Function of quicksort itself
/**
* 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;
}
continues in infinite loop..
– Diogo Neiss