Contagem de Comparações e Trocas

Alexandra241
(usa Debian)

Enviado em 29/03/2013 - 16:31h

Boa tarde a todos! Estou precisando de ajuda pra contar as comparações feitas no algoritmos de ordenação insertsort, shellsort, quicksort e heapsort! No insert por exemplo já tentei de diversas maneiras..ele deve dar o mesmo número de comparações feitas no bubblesort e no select sort, não?

Aqui está minha implementação do insert! :

void InsertSort(Item *vet, int N) {

int i, j;
Item aux;
int compara=0;
int movimenta=0;

for (i = 1; i < N; i++) {

aux = vet[i];
j = i - 1;

if(aux.Chave < vet[j].Chave)
compara++;
while ((j >= 0) && (aux.Chave < vet[j].Chave)) {


vet[j + 1] = vet[j];
j--;
movimenta++;
}
vet[j + 1] = aux;

}
printf("O vetor ordenado:\n");
for (i = 0; i < N; i++) {

printf(" %d", vet[i]);

}
printf("\n\nComparações: %d \nMovimentações: %d\n", compara, movimenta);
}

se alguém puder me dar uma ideia de como contar certinho.. :)

removido
(usa Nenhuma)

Enviado em 29/03/2013 - 23:03h

Use uma variável estática com auto-incremento.

"função" compara (...) {



	static int acessos;



	(...)



	acessos++;



} 

Uma variável estática só é visível apenas dentro da função em que ela está.
E o valor permanece, mesmo se sair da função.
Então cada vez que a função de comparação for acessada, ela se auto-incrementa.

Só fica faltando um jeito de você retornar a contagem.
Pode ser com uma função especialmente feita prá contar.
E que é acessada de fora do comparador apenas prá usar um "return" com esse valor.

E quanto aos métodos, o que torna um método mais rápido que outro?
Menor número de comparações ou menor número de troca de posições?

Alexandra241
(usa Debian)

Enviado em 29/03/2013 - 23:18h

Depende do algoritmo, em alguns casos como o próprio insert é bem custoso fazer movimentações se você tiver um vetor que não está quase ordenado..

Mas então você me indica fazer uma função separada? É que já queria embutir no código!

Por ex.

while ((j >= 0) && (aux.Chave < vet[j].Chave)) {


vet[j + 1] = vet[j];
j--;
movimenta++;
}

Nesse trecho tenho movimentações sucessivas..dentro de um array! E a cada passada ele compara! E já troca caso necessário...Quero algo mais direto! Enfim..

Alexandra241
(usa Debian)

Enviado em 29/03/2013 - 23:25h

Veja bem a minha implementação no select sort!

void SelectSort(Item *vet, int N) {

int compara = 0;
int movimenta = 0;
int i, j, min;
Item aux;

for (i = 0; i < N - 1; i++) {
min = i;
for (j = 1 + i; j < N; j++) {
compara++;
if (vet[j].Chave < vet[min].Chave) {
min = j;
movimenta++;
}
aux = vet[min];
vet[min] = vet[i];
vet[i] = aux;
}
}

printf("O vetor ordenado:\n");
for (i = 0; i < N; i++) {

printf(" %d", vet[i]);

}
printf("\n");
printf("\n\nComparações: %d \nMovimentações: %d\n", compara, movimenta);
printf("\n");

}

O caso é que no insert, para um array de mesmo tamanho, o número de comparações feitas deveria ser o mesmo do select e do bubblesort e eu não tô sabendo como contar no insert! Todas as comparações feitas!

removido
(usa Nenhuma)

Enviado em 29/03/2013 - 23:43h

void InsertSort(Item *vet, int N) {



	int i, j;

	Item aux;

	int compara=0;

	int movimenta=0;



	for (i = 1; i < N; i++) {



		aux = vet;

		j = i - 1;



		if(aux.Chave < vet[j].Chave)

			compara++;



		while ((j >= 0) && (aux.Chave < vet[j].Chave)) {



			vet[j + 1] = vet[j];

			j--;



			movimenta++;

		}



		vet[j + 1] = aux;



	}



	printf("O vetor ordenado:\n");



	for (i = 0; i < N; i++) {

		printf(" %d", vet);

	}



	printf("\n\nComparações: %d \nMovimentações: %d\n", compara, movimenta);



} 

Eu estava pensando nos algoritmos separados em pedaços (funções) e usando esses pedaços em comum quando necessários, para efeito de contagem em conjunto.

Você só considera como comparação quando os valores de referência da comparação (chave) são menores?

		if(aux.Chave < vet[j].Chave)

			compara++; 

Na primeira função a contagem está antes:

            compara++;

            if (vet[j].Chave < vet[min].Chave) {

                min = j;

                movimenta++;

            } 

Veja se é isso.

removido
(usa Nenhuma)

Enviado em 29/03/2013 - 23:44h

putz ... estou vendo javascript aqui. :\