C Método da bolha em c

[Leanderson Pinheiro]

Gente como eu faço para contar quantas vezes foi feita a troca dentro do método da bolha ?

[JorgeGus]

@Leanderson Pinheiro Numa situação real você poderia simplesmente criar um contador inicializado com 0 e incrementar esse contador a cada permutação de posição.

 

Mas se o que você quer é calcular a complexidade desse algoritmo de forma mais teórica, aí pessoalmente não tenho como ajudar.

[Leanderson Pinheiro]

@JorgeGus

Eu quero apenas contar quantas vezes ele foi percorrido apenas, mas a saída saí errada

código abaixo:

#include <stdio.h>

int main()
{
    // foram definidas as variáveis//
    int vetor[100], x =0, y=0, aux=0;
    int n;
    int cont=0;

    // scanf para determinar a quantidade lida
    scanf("%d",&n);

// faz o vetor = auxiliar
    for( x = 0; x < n; x++ )
    {
        scanf("%d",&aux);
        vetor[x] = aux;
    }

    // faz a ordem decrescente
    for( x = 0; x < n; x++ )

    {

        for( y = x + 1; y < n; y++ )
        {

            if ( vetor[y] > vetor[x] )
            {
                aux = vetor[y];
                vetor[y] = vetor[x];
                vetor[x] = aux;

            }

        }
    }

    // exibe os elementos ordenados
    for( x = 0; x < n; x++ )
    {
        printf("%d\n",vetor[x]); // exibe o vetor ordenado

    }
    // printa quantas vezes percorreu
    printf("%d\n", cont/2);

    // caso não percorra nenhuma vez//
    if(cont<1)
    {
        printf("1\n");
    }

    return 0;
}
 

[JorgeGus]

Seria isso?

 #include <stdio.h>

int main() {
    int vetor[100], x =0, y=0, aux=0;
    int n;
    int cont=0;
    int comp = 0;
    int trocas = 0;
    printf("Numero de elementos: ");
    scanf("%d",&n);
    for(x = 0; x < n; x++) {
        printf("n%d: ", x + 1);
        scanf("%d",&aux);
        vetor[x] = aux;
    }
    printf("\n");
    for(x = 0; x < n - 1; x++) {
        cont++;
        for(y = x + 1; y < n; y++) {
            comp++;
            if (vetor[y] > vetor[x]) {
                trocas++;
                aux = vetor[y];
                vetor[y] = vetor[x];
                vetor[x] = aux;
            }
        }
    }

    for( x = 0; x < n; x++ ) {
        printf("%d\n",vetor[x]);
    }
    printf("\npercorrido: %d\n", cont);
    printf("\ncomparacoes: %d\n", comp);
    printf("\ntrocas: %d\n", trocas);
    return 0;
}

O número de vezes que o vetor é percorrido e o número de comparações é sempre o mesmo para o mesmo número de elementos, apenas o número de trocas pode variar de acordo com o valor de cada elemento. E o vetor é percorrido a cada giro do loop apenas de forma parcial.

 

Alterei a linha

    for( x = 0; x < n; x++ )

para

    for(x = 0; x < n - 1; x++)

porque na última execução o loop interno nunca seria executado já que nesse caso y "(x + 1)" seria igual a n.

[Leanderson Pinheiro]

@JorgeGus @JorgeGusentrada: 5
1 2 3 4 5

 

saída: 5 4 3 2 1

nperco: 5

seriam essas as saídas, mas não to conseguindo acho q necessita de quando tiver ordenado já parar o código.

 

[JorgeGus]

@Leanderson Pinheiro Nesse algorítmo você só tem certeza que o vetor está ordenado quando ele termina de ser executado, não é possível parar antes porque você não vai saber se o vetor está ou não ordenado.

 

Você pode retirar o "-1" que eu adicionei no primeiro for da ordenação para que ele tente percorrer o vetor uma vez a mais, isso não vai influenciar nas comparações, já que o segundo for não vai ser executado, mas assim você consegue o resultado que postou.

[Leanderson Pinheiro]

@JorgeGus @JorgeGus Cara, resolve só pra esse caso tirando o -1. Mas eu basicamente queria um que percorresse só até ficar ordenado, e contasse só até ai sacou ?

[JorgeGus]

@Leanderson Pinheiro Agora entendi, mas nesse caso acho que você vai ter que mudar o algoritmo que está usando. Esse algoritmo que você postou me parece ser o "Selection Sort", que possui um número de comparações fixas de acordo com o número de elementos. No "Bubble Sort" por exemplo você vai varrendo o vetor até que não haja mais elementos a serem trocadados de lugar, então de fato você pode interromper o algoritmo quando ele estiver ordenado, mas existem muitos outros algoritmos de ordenação.

 

Descrição do "Bubble Sort":

https://pt.wikipedia.org/wiki/Bubble_sort

[arfneto]

2 horas atrás, Leanderson Pinheiro disse:

Eu quero apenas contar quantas vezes ele foi percorrido apenas, mas a saída saí errada

 

Talvez possa definir melhor as coisas à medida em que escreve ou programa.

 

O que você tentou fazer no loop é mostrar a quantidade de trocas, e isso depende da configuração do vetor na entrada. No pior caso ele pode estar ordenado ao contrário. No melhor caso ele já está em ordem e não vai trocar nadinha.

 

Exemplo: um vetor de 10 int diferentes
 

No pior caso vai fazer 45 trocas, no melhor nenhuma, claro.

 

Só que nesse caso o programa como escreveu vai calmamente passar pelo loop à toa todas as vezes. Por isso tem gente que escreve sobre um hipotético bubble sort otimizado que talvez seja o que está procurando.

 

Na verdade esse deveria ser o método comum e o original deveria ser chamado de bubble sort ingênuo, porque é muito bobinho ficar rodando o algoritmo depois de o vetor está ordenado. Não é otimizado parar quando já está ordenado: só não é 1d10t@. O normal é parar.

 

Para evitar isso apenas conte quantas trocas fez no loop interno e saia se não fez nenhuma.

 

O ingênuo seria
 

#include <stdio.h>
int main(void)
{
    int vetor[10] = { 0,1,2,3,4,5,6,7,8,9 }; // pior caso
    //int vetor[10] = { 9,8,7,6,5,4,3,2,1 }; // melhor caso
    //  int vetor[10] = { 9,8,7,6,5,4,3,1,2 }; // uma troca faltando
    int n = 10;
    printf("Vetor original: "); 
    for( int x = 0; x < n; x+=1 ) printf("%d ",vetor[x]);
    printf("\n");

    int trocas=0;
    int x = 0;
    // classifica em ordem decrescente
    for( x = 0; x < n-1; x+=1 )
    {
        for( int y = 0; y < n - x - 1; y+=1 )
        {
            if ( vetor[y] < vetor[y+1] )
            {
                trocas+= 1;
                int aux = vetor[y];
                vetor[y] = vetor[y+1];
                vetor[y+1] = aux;
            }
        };  // for(y)
    };  // for(j)

    printf("Vetor ordenado: "); 
    for( int x = 0; x < n; x+=1 ) printf("%d ",vetor[x]);
    // printa quantas vezes percorreu
    printf("\nTotal de %d trocas", trocas);
    return 0;
}

 

E compare com o que escreveu

 

No entanto o normal é escrever assim

 

#include <stdio.h>
int main(void)
{
    int vetor[10] = { 0,1,2,3,4,5,6,7,8,9 }; // pior caso
    //int vetor[10] = { 9,8,7,6,5,4,3,2,1 }; // melhor caso
    //  int vetor[10] = { 9,8,7,6,5,4,3,1,2 }; // uma troca faltando
    int n = 10;
    printf("Vetor original: "); 
    for( int x = 0; x < n; x+=1 ) printf("%d ",vetor[x]);
    printf("\n");

    int trocas=0;
    int x = 0;
    // classifica em ordem decrescente
    for( x = 0; x < n-1; x+=1 )
    {
        int controle = 0;
        for( int y = 0; y < n - x - 1; y+=1 )
        {
            if ( vetor[y] < vetor[y+1] )
            {
                trocas+= 1;
                int aux = vetor[y];
                vetor[y] = vetor[y+1];
                vetor[y+1] = aux;
                controle = 1;
            }
        };  // for(y)
        if ( controle == 0 )
        {
            printf( "\
saindo com x = %d e %d trocas efetuadas, porque o vetor esta em ordem\n", x, trocas);
            break;
        }
    };  // for(j)

    printf("Vetor ordenado: "); 
    for( int x = 0; x < n; x+=1 ) printf("%d ",vetor[x]);
    // printa quantas vezes percorreu
    printf("\nTotal de %d trocas", trocas);
    return 0;
}

 

E essa variável controle faz o simples:

• se durante o loop ela não mudou não trocou ninguém.
• Se não trocou ninguém está em ordem
• Se está em ordem pare de rodar

Exemplo

 

	int vetor[10] = { 9,8,7,6,5,4,3,1,2 }; // uma troca faltando

 

É óbvio que tem que sair depois de uma única troca, o 2 pelo 1
 

Vetor original: 9 8 7 6 5 4 3 1 2 0 
saindo com x = 1 e 1 trocas efetuadas, porque o vetor esta em ordem
Vetor ordenado: 9 8 7 6 5 4 3 2 1 0 
Total de 1 trocas

 

E vai descobrir com x = 1

 

Eu postei um método animado com bubble sort nesse forum tempos atrás. Pesquise nas coisas que eu publiquei. Tem um botão no forum. O programa mostra um vetor colorido e uma animação com as trocas.

 

Exemplo
 

    int vetor[10] = { 9,8,7,6,5,4,3,2,1 }; // melhor caso

 

Pois é: não vai trocar nadinha

 

Vetor original: 9 8 7 6 5 4 3 2 1 0 
saindo com x = 0 e 0 trocas efetuadas, porque o vetor esta em ordem
Vetor ordenado: 9 8 7 6 5 4 3 2 1 0
Total de 0 trocas

 

Sobre seu programa

 

Não perca tempo lendo valores em programas que ainda não estão prontos. Não vai aprender nada e só vai perder tempo

 

TESTE o retorno de scanf() sempre

 

declare as variáveis de controle do loop no próprio for

 

mostre as coisas que está lendo

 

 

 

Aí tem o programa. Eis uma imagem