Contador

22 de outubro de 2019 4 respostas

joaostm 22 de outubro de 2019

Adicionei um contador comp++ neste método de ordenação para que seja incrementado e, ao final, exiba quantas comparações foram realizadas. No entanto, o que ele apresenta é, em quantidade de impressões, quantas comparações foram feitas.
Exemplo: Se resultaram 30 comparações, ele não exibe 30, mas imprime trinta vezes COMP: 1. E sim, verifiquei, e a impressão não está dentro do while.

public class QuickSort1 {
  
  public static void quickSort(int v[], int esquerda, int direita) {
    int esq = esquerda;
    int dir = direita;
    int pivo = v[(esq + dir) / 2];
    int troca;
    int comp = 0;

    while (esq <= dir) {
      while (v[esq] < pivo) {
        esq = esq + 1;
      }
      while (v[dir] > pivo) {
        dir = dir - 1;
      }
        if (esq <= dir) {
          troca = v[esq];
          v[esq] = v[dir];
          v[dir] = troca;
          esq = esq + 1;
          dir = dir - 1;
        }
    comp++;
    }
 
    if(dir > esquerda)
      quickSort(v, esquerda, dir);
    if(esq < direita)
      quickSort(v, esq, direita);
  System.out.println("COMP: "+comp);
  }
  
  public static void main(String args[]) {
  int vet_size = 2;
  int numbers[] = new int[vet_size];
    for(int i=0; i<vet_size; i++) {
      numbers[i] = i;
    }
    quickSort(numbers, 0, vet_size - 1);
      for(int i = 0; i < vet_size; i++) {
        System.out.println("Number["+i+"] = "+numbers[i]);
      }
  }
}

4 Respostas

Iohannes 22 de out. de 2019

O seu contador comp está declarado e inicializado dentro do método recursivo. Logo, toda chamada reinicializa o contador com zero. Você pode declarar o contador como um campo (variável da classe). Para exemplificar, tomei a liberdade de fazer algumas alterações:

import java.util.Random;

public class QuickSort{
	private static int comp = 0;
	
	public static void quickSort(int v[], int esquerda, int direita){
		int esq = esquerda;
		int dir = direita;
		int pivo = v[(esq + dir) / 2];
		int troca;
		
		while (esq <= dir){
			while (v[esq] < pivo){
				esq = esq + 1;
			}
		  
			while (v[dir] > pivo){
				dir = dir - 1;
			}
			
			if (esq <= dir){
				troca = v[esq];
				v[esq] = v[dir];
				v[dir] = troca;
				esq = esq + 1;
				dir = dir - 1;
			}
			comp++;
		}
	 
		if(dir > esquerda)
		  quickSort(v, esquerda, dir);
	  
		if(esq < direita)
		  quickSort(v, esq, direita);
	}
  
	public static void main(String args[]){
		int vet_size = 5;
		int numbers[] = new int[vet_size];
		Random random = new Random();
		
		System.out.println("\nVetor original: ");
		for(int i = 0; i < vet_size; i++){
			numbers[i] = 1 + random.nextInt(vet_size );
			
			System.out.println("Number[" + i + "] = " + numbers[i]);
		}
		
		quickSort(numbers, 0, vet_size - 1);
		
		System.out.println("\nComparações: " + comp + "\n");
		for(int i = 0; i < vet_size; i++){
			System.out.println("Number[" + i + "] = " + numbers[i]);
		}
	}
}

Rodando…

igorrds 22 de out. de 2019

Tenta isso, o contador fica nas comparações, mas a impressão é feita apenas no método main.

public class QuickSort{
	private static int comp = 0;
	
	public static void quickSort(int v[], int esquerda, int direita) {
	    int esq = esquerda;
	    int dir = direita;
	    int pivo = v[(esq + dir) / 2];
	    int troca;
	    

	    while (esq <= dir) {
	      while (v[esq] < pivo) {
	        esq = esq + 1;
	      }
	      while (v[dir] > pivo) {
	        dir = dir - 1;
	      }
	        if (esq <= dir) {
	          troca = v[esq];
	          v[esq] = v[dir];
	          v[dir] = troca;
	          esq = esq + 1;
	          dir = dir - 1;
	        }
	    comp++;
	    }
	 
	    if(dir > esquerda)
	      quickSort(v, esquerda, dir);
	    if(esq < direita)
	      quickSort(v, esq, direita);
	  
	  }
	  
	  public static void main(String args[]) {
	  int vet_size = 10;
	  int numbers[] = new int[vet_size];
	    for(int i=0; i<vet_size; i++) {
	      numbers[i] = i;
	    }
	    quickSort(numbers, 0, vet_size - 1);
	      for(int i = 0; i < vet_size; i++) {
	        System.out.println("Number["+i+"] = "+numbers[i]);
	      }
	      System.out.println("COMP: "+comp);
	  }

}

joaostm 22 de out. de 2019

Obrigado. Mas, da forma que você propôs, o que ele fará será basicamente mostrar quantos índices há no vetor.

igorrds 22 de out. de 2019

Eu editei, da uma olhada. Mas acho que a resolução do @Iohannes seja algo mais sofisticado.

Criado 22 de outubro de 2019

Ultima resposta 22 de out. de 2019

Respostas 4

Participantes 3

4 Respostas

Topicos relacionados