Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

1. Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 28/10/2020 - 23:45h

Boa noite pessoal.

Estou fazendo um código para fazer ordenações em um vetor usando os algoritmos de ordenação, selection, insertion ... Estou com dificuldades para entender onde deveria colocar os contadores, do jeito que estou pensando eles saem zerados. Poderiam me explicar onde estou errando ? Desde já agradeço a ajuda de todos.

#include <stdio.h>
#include <stdlib.h>

void selection_sort(int *v, int tam);
void insertion_sort(int *v, int tam);

int main() {

int i;
int v[10] = {2, 5, 6, 1, 7, 4, 9, 8, 10, 3};

printf("\n");

printf("\nVetor inicial: \n");
for (i = 0; i < 10; i++)
{
printf("%d ", v[i]);
}

printf("\n");

printf("\nInsertion sort:");
insertion_sort(v, 10);

for (i = 0; i < 10; i++)
{
printf("%d ", v[i]);
}

printf("\n");

printf("\n");

return 0;
}

void insertion_sort(int *v, int tam) {

int i, j, pivo, trocas, comp;

trocas = 0;
comp = 0;

for ( i = 1; i < tam; i++)
{
pivo = v[i];
j = i - 1;

while (j >= 0 && v[j] > pivo)
{

v[j + 1] = v[j];
j--;
trocas++;
comp++;
}


v[j+1] = pivo;

}

printf("\nTrocas: %d Comparações: %d\n", trocas, comp);
}



  


2. MELHOR RESPOSTA

Stanislaus K
StanislausK

(usa FreeBSD)

Enviado em 31/10/2020 - 11:39h

Ola,

"Estou com dificuldades para entender onde deveria colocar os contadores, do jeito que estou pensando eles saem zerados. Poderiam me explicar onde estou errando ?"

Voce entende porque saem zerados para a função insertion_sort? Está correto em sairem zerados, da maneira como você escreveu o código... O problema esta no main!

Voce tem APENAS UM VETOR que irá ser usado para duas funções: selection_sort e insertion_sort.

Quando passa pela primeira função (selection_sort) ocorrem as trocas e comparações e os valores do vetor ficam organizados, certo?

DE: 2 5 6 1 7 4 9 8 10 3
PARA: 1 2 3 4 5 6 7 8 9 10

Com esse vetor organizado, passa em seguida para a segunda função (insertion_sort)... Como o vetor já foi organizado, obviamente haverá 0 trocas e 0 comparações! Entendeu?

Você teria que ter dois vetores, cada um direcionado para sua respectiva função...




3. Re: Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 29/10/2020 - 00:01h

So corrigindo pessoal, abaixo está o código completo, tenho o selection sort e o insertion sort implemetados. No primeiro as contagem da certo, já no segundo não.

#include <stdio.h>
#include <stdlib.h>

void selection_sort(int *v, int tam);
void insertion_sort(int *v, int tam);

int main() {

int i;
int v[10] = {2, 5, 6, 1, 7, 4, 9, 8, 10, 3};

printf("\n");

printf("\nVetor inicial: \n");
for (i = 0; i < 10; i++)
{
printf("%d ", v[i]);
}

printf("\n");

printf("\nSelection sort:");
selection_sort(v, 10);

for (i = 0; i < 10; i++)
{
printf("%d ", v[i]);
}
printf("\n");

printf("\nInsertion sort: \n");
insertion_sort(v, 10);

for (i = 0; i < 10; i++)
{
printf("%d ", v[i]);
}

printf("\n");

printf("\n");

return 0;
}

void selection_sort(int *v, int tam) {

int i, j, min, pivo, comp, trocas;

comp = 0;
trocas = 0;

for (i = 0; i < (tam - 1); i++)
{
min = i;
for ( j = (i+1); j < tam; j++)
{
if (v[j] < v[min])
{
min = j;
comp++;
}

}

if (i != min)
{
pivo = v[i];
v[i] = v[min];
v[min] = pivo;
trocas++;
}


}

printf("\nTrocas: %d Comparações: %d\n", trocas, comp);
}

void insertion_sort(int *v, int tam) {

int i, j, pivo, trocas, comp;

trocas = 0;
comp = 0;

for ( i = 1; i < tam; i++)
{
pivo = v[i];
j = i - 1;

while (j >= 0 && v[j] > pivo)
{

v[j + 1] = v[j];
j--;
trocas++;
comp++;
}


v[j+1] = pivo;

}

//printf("\nTrocas: %d Comparações: %d\n", trocas, comp);
}



4. Re: Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 31/10/2020 - 12:06h

Agora entendi !!! então poderia me dar um dica pra melhor organizar o código ? Seria melhor eu colocar o mais vetores desordenados, um pra cada método ou vetores pivos, para receber os vetores ordenados ? Haveria um jeito de usar um só vetor ?




5. Re: Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 31/10/2020 - 12:21h

Mudaria se eu ao invés de passar o ponteiro do vetor como parâmetro, eu passasse o próprio vetor ?


6. Re: Contagem comparações e trocas em uma função de ordenação

Stanislaus K
StanislausK

(usa FreeBSD)

Enviado em 31/10/2020 - 13:06h

Ola,

"Haveria um jeito de usar um só vetor?"

sim... voce pode colocar cada valor dentro do vetor, com numero fixo, no seu caso 10, ou um número variável usando malloc (nesse caso você precisaria inserir o número de valores desejado previamente)...

e voce poderia criar um menu (usando if/else), para selecionar uma função de cada vez, juntamente com um loop do/while, para que você sempre faça um retorno ao menu... assim você pode usar diversas vezes o seu código, onde para cada vez você seleciona uma função diferente... seria bom usar um limpador de tela para cada retorno...

se tiver ainda alguma dúvida?


7. Re: Contagem comparações e trocas em uma função de ordenação [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 31/10/2020 - 13:11h

Entendi, muito obrigado !!!