Quicksort in double chained list

Question

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;
    }

Answer 1

Try to change:

if (esq < j)

for:

if (j > esq)

and

comparacoes += quicksort(esq, j);

for:

comparacoes += quicksort(esq, j + 1); // A direita da próxima partição deve ser o índice posterior ao j.

Another problem I found is that you are not limiting i and j to stop only on the current quicksort partition:

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++);

for:

for(CelulaDupla tmp = this.elementoNaPosicao(i); tmp.elemento.getApelido().compareTo(pivo.elemento.getApelido()) < 0 && i < dir; tmp = tmp.prox, i = i+1, comparacoes++);
for(CelulaDupla tmp = this.elementoNaPosicao(j); tmp.elemento.getApelido().compareTo(pivo.elemento.getApelido()) > 0 && j > esq; tmp = tmp.ant, j = j-1, comparacoes++);