Dúvida sobre contador no método de ordenação QuickSort [Resolvido]

[LarissaVelsa]

Boa noite, pessoal!

A dúvida é o sequinte: Tenho o método de ordenação do tipo quicksort e preciso contar o número de trocas que ele faz até a ordenação completa do vetor. O código roda, mas não mostra o número de trocas (coloquei um contator: contquick ++, porém dá
resultado zero, de zero ordenação. Ah, passo no método principal o seguinte para o método do quick, através de parâmetro: or.quick_sort(vetor, ini, fim); Resumindo: o vetor é ordenado usando este método, só que não as contabiliza. Quero saber como faço para resolver.

    public static void quick_sort(int[] v, int ini, int fim) {
        int meio;
        int contquick1=0;
        int contquick2=0;
        int contquick = 0;
        int t = 0;

       for (int i = ini; i <= fim; i++) {
           
            meio = partition(v, ini, fim); // meio recebe partition (vetor, ini e fim)
            quick_sort(v, ini, meio);
         
            quick_sort(v, meio + 1, fim);
             contquick ++;
                
        
             }
        
       
        
        for (int i = 0; i < (v.length) - 1; i++) {
            System.out.println(v[i]);

        }

        System.out.println("Quantidade de trocas do quick: " + contquick);
    }

    public static int partition(int[] v, int ini, int fim) {
        int pivo, topo, i;

        pivo = v[ini];
        topo = ini;

        for (i = ini + 1; i <= fim; i++) {
            if (v[i] < pivo) {
                v[topo] = v[i];
                v[i] = v[topo + 1];
                topo++;
                
            }
        }
        v[topo] = pivo;

        return topo;
    } // fim da quick

[antoniofilho]

Larissa, dentro do metodo quick_sort você deve retirar esse for e incluir uma condição que ini deve ser menor que fim, porque senão entra e estora a exception java.lang.StackOverflowError, para contar a quantidade de vezes que o metodo é chamado basta declarar esse contquick de fora do metodo quick_sort.

segue abaixo o code como ficaria:

    static int contquick=0;
    public static void quick_sort(int[] v, int ini, int fim) {
        int meio;
        contquick ++;
        if (ini < fim) {
              meio = partition(v, ini, fim); // meio recebe partition (vetor, ini e fim)
              quick_sort(v, ini, meio);
	       quick_sort(v, meio + 1, fim);
        }
        
        for (int i = 0; i < (v.length) - 1; i++) {
        	System.out.println(v[i]);
        }
        

        System.out.println("Quantidade de trocas do quick: " + contquick);
    }

    public static int partition(int[] v, int ini, int fim) {
        int pivo, topo, i;

        pivo = v[ini];
        topo = ini;

        for (i = ini + 1; i <= fim; i++) {
            if (v[i] < pivo) {
                v[topo] = v[i];
                v[i] = v[topo + 1];
                topo++;
                
            }
        }
        v[topo] = pivo;

        return topo;
    } // fim da quick

[regis_hideki]

O importante é entender porque o contador não funciona dessa maneira.

Veja que a função é recursiva, dessa forma, cada chamada recursiva terá sua própria variável local “contador”, ou seja, o que parece ser a mesma variável é, na verdade, um conjunto de variáveis com mesmo nome e que é descartada cada vez que a chamada recursiva chega ao fim. Deixando a variável como atributo da classe, todas as chamadas recursivas incrementarão a mesma variável.

Note que, por ser recursiva, o seu print deveria aparecer várias vezes. Se está imprimindo apenas uma, aparenta estar com erro.

Aproveitando o tópico, alguém sabe se existe outro jeito de se trabalhar com recursão sem precisar ficar criando variáveis globais ou passando parâmetros de saída? Tento evitar ambos ao máximo, mas com recursão, não vejo outro jeito.

[entanglement]

Linguagens como Lisp e Scala têm suporte melhor a recursão porque as estruturas de dados que eles usam suportam melhor a recursão.

Java é meio desajeitado nesse ponto; C++ só não é pior nesse ponto porque ele suporta parâmetros de saída.

Em Java, normalmente para fazer uma função recursiva você precisa de duas funções - uma que faz o setup e outra que realmente executa a parte recursiva.

Quicksort “recursivo” é algo que se escreve em Java apenas para se mostrar como funciona o algoritmo; na prática, usa-se uma versão iterativa desse algoritmo, até porque o suporte a recursão do Java é bem ruinzinho, por sinal (por exemplo, não há tail calls, então algoritmos com altos graus de recursividade falham rapidamente por estouro de pilha.)

[regis_hideki]

[quote=entanglement]Linguagens como Lisp e Scala têm suporte melhor a recursão porque as estruturas de dados que eles usam suportam melhor a recursão.

Java é meio desajeitado nesse ponto; C++ só não é pior nesse ponto porque ele suporta parâmetros de saída.

Em Java, normalmente para fazer uma função recursiva você precisa de duas funções - uma que faz o setup e outra que realmente executa a parte recursiva.

Quicksort “recursivo” é algo que se escreve em Java apenas para se mostrar como funciona o algoritmo; na prática, usa-se uma versão iterativa desse algoritmo, até porque o suporte a recursão do Java é bem ruinzinho, por sinal (por exemplo, não há tail calls, então algoritmos com altos graus de recursividade falham rapidamente por estouro de pilha.)
[/quote]

Quando se referiu à passagem de parâmetros de saída no C++, está comentando sobre passagem de ponteiros? Ou há outro jeito?

Essa de usar uma função de setup é uma boa… assim, o método “feio”, que recebe parâmetros de saída pode ficar escondido em um método privado, enquanto a função de setup, (pública, por exemplo), inicializa, passa ao método privado, recebe o parâmetro de saída e devolve ao chamador da forma mais intuitiva, ou seja, através do retorno.

[LarissaVelsa]

[quote=antoniofilho]Larissa, dentro do metodo quick_sort você deve retirar esse for e incluir uma condição que ini deve ser menor que fim, porque senão entra e estora a exception java.lang.StackOverflowError, para contar a quantidade de vezes que o metodo é chamado basta declarar esse contquick de fora do metodo quick_sort.

segue abaixo o code como ficaria:

[code]
static int contquick=0;
public static void quick_sort(int[] v, int ini, int fim) {
int meio;
contquick ++;
if (ini < fim) {
meio = partition(v, ini, fim); // meio recebe partition (vetor, ini e fim)
quick_sort(v, ini, meio);
quick_sort(v, meio + 1, fim);
}

    for (int i = 0; i < (v.length) - 1; i++) {
    	System.out.println(v[i]);
    }
    

    System.out.println("Quantidade de trocas do quick: " + contquick);
}

public static int partition(int[] v, int ini, int fim) {
    int pivo, topo, i;

    pivo = v[ini];
    topo = ini;

    for (i = ini + 1; i <= fim; i++) {
        if (v[i] < pivo) {
            v[topo] = v[i];
            v[i] = v[topo + 1];
            topo++;
            
        }
    }
    v[topo] = pivo;

    return topo;
} // fim da quick

[/code][/quote]

Correto, utilizei o código acima. Porém ainda há um problema: loops. Quando o algoritmo e executado, aparece mais do que uma vez. O necessário é mostrar o vetor ordenado e o contador já totalizado e não ele ir mostrando no decorrer da execução do algoritmo. Como posso fazer para não ficar dentro deste loop, usando este mesmo raciocínio de algoritmo?

[entanglement]

Larissa, se esse é seu problema, simplesmente imprima o vetor ordenado FORA do método quick_sort.

(Usualmente, a menos que seja para efeitos de demonstrar o que ocorre durante a execução de um programa, não se imprime nada dentro desses algoritmos genéricos, como os de ordenação. )

[ViniGodoy]

Por favor, ao postar tópicos, NÃO DEIXE O TÍTULO SOMENTE COM LETRAS MAIÚSCULAS.

[entanglement]

Usando seu código, faríamos algo assim:

package guj;

public class QuickSort {
    private int contquick;

    public void quick_sort(int[] v, int ini, int fim) {
        int meio;
        contquick++;
        if (ini < fim) {
            meio = partition(v, ini, fim); // meio recebe partition (vetor, ini e fim)
            quick_sort(v, ini, meio);
            quick_sort(v, meio + 1, fim);
        }
    }

    private int partition(int[] v, int ini, int fim) {
        int pivo, topo, i;

        pivo = v[ini];
        topo = ini;

        for (i = ini + 1; i <= fim; i++) {
            if (v[i] < pivo) {
                v[topo] = v[i];
                v[i] = v[topo + 1];
                topo++;
            }
        }
        v[topo] = pivo;

        return topo;
    }
    
    public int getCont() { return contquick; }
    
    public QuickSort () {
        contquick = 0;
    }
}

package guj;

public class ExemploQuickSort {

    private static void print (int[] v, int ini, int fim) {
        for (int i = ini; i <= fim; i++) {
            System.out.printf ("%4d,", v[i]);
        }
        System.out.println();
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] dados = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2};
        QuickSort qs = new QuickSort();
        qs.quick_sort (dados, 0, dados.length-1);
        System.out.printf("O quicksort efetuou %d %n", qs.getCont());
        print (dados, 0, dados.length - 1);
    }

}