C Meu programa começou dar errado depois de usar cálculo de tempo de execução

Esnack · 26 de fevereiro de 2018

Meu bubble shot estava dando certo até colocar o cálculo de tempo de execução de programa, depois disso não estava apresentando os 1000 elementos ordenados apenas alguns.

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

int main()
{

    int x , y , aux;
    int n;
    int vetor[1000];
    float tempo_execucao;

    clock_t inicio,fim;

    //CONTADOR 1 ao 1000
    for (x = 1000; x >=1; x--) {
    vetor[x] = rand()%1000;
    }


    inicio = clock();
    //BUBBLE SHOT
    for (x = 1; x < n; x++)
    {

        for (y = 0; y < n - x; y++)
        {

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

            }

        }
    }
    fim = clock();

    //IMPRESSÃO DOS NÚMEROS
    for (x = 1; x < n; x++){
        printf("%d\t",x);


    }


    tempo_execucao = (fim-inicio)*1000/CLOCKS_PER_SEC;
    printf("\n\nTempo de execução do programa: %f",tempo_execucao);


    return 0;
}

Ansi C · 26 de fevereiro de 2018

@Esnack Olá!

5 horas atrás, Esnack disse:

Meu bubble shot estava dando certo até colocar o cálculo de tempo de execução de programa, depois disso não estava apresentando os 1000 elementos ordenados apenas alguns.

Aperta Ctrl+Z no editor e volta no tempo.

Ou melhor leia este artigo Wikipédia acerca do algoritmo de ordenação Bubble sort. De início você verá que o loop de ordenação não para enquanto houver substituição feita, já o seu algoritmo diminui a cada incremento do x. Ou seja, por um detalhe apenas.

Simon Viegas · 26 de fevereiro de 2018

Olá @Esnack.

Então, ou já não estava funcionando antes, ou você mudou além de onde deveria... o uso do cálculo do tempo não tem interferência alguma.

Minha sugestão:

Revise seu código código, veja qual comportamento está errado e atue nele. Por exemplo:

Peguei o seu código e apenas rodei aqui, deu isso:

Tempo de execução do programa: 0.000000
--------------------------------
Process exited after 0.03777 seconds with return value 0
Pressione qualquer tecla para continuar. . .

Ou seja, não bate com a sua descrição do erro:

8 horas atrás, Esnack disse:

não estava apresentando os 1000 elementos ordenados apenas alguns.

RESUMINDO:

Poste o que você acha que está errado, ex.:

Citação

Pessoal, ao tentar imprimir não está exibindo os resultado na tela

ou

Citação

Não sei o que está acontecendo... ao imprimir os números estão simplesmente sendo impressos em ordem crescente. Como se os números sorteados fossem exatamente de 1 a 1000... sem números repetidos. Tá estranho.

Veja, o que importa é o problema e não a partir de qual momento passou a dar problema... ou seja, essa descrição serve para ter uma base do problema em si (que não ficou claro)... se fosse isso, como sugerido por @Mauro Britivaldo, retire o trecho do tempo e volta para o que estava antes... sacou? Tecnicamente você só postou um código e disse que não está funcionando... é necessário especificar melhor "o quê não está funcionando".

Mas para adiantar, vamos lá:

Você está usando n no último for, mas não inicializou a variável, ou seja, n está provavelmente com 0; Use algo como:

int n=100;

obs.: deixe com 100 mesmo, mais fácil para testar... mais pra frente, mude pra 1000. Isso resolve o erro de "não aparecer nada";

Ah! lá no primeiro for, use x = n... em vez de x=1000.

Faça essa alteração, teste o programa algumas vezes e vê se está tudo certo, caso não, tente encontrar o erro e corrigir. Aí, posta o código atual e onde está com dúvidas... ou o "código final" para revisarmos e também servi de base para outro usuários.

No aguardo.

Esnack · 26 de fevereiro de 2018

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


int main()
{

    int x , y , aux;
    int n=1000;
    int vetor[1000];
    double tempo_execucao;


    clock_t inicio,fim;

    //CONTADOR QUE GERA NÚMEROS ALEATÓRIOS
    for (x = 0; x < 1000; x++) {
    vetor[x] = rand()%100;
    }


     inicio = clock();
    //BUBBLE SHOT
    for (x = 1; x < n; x++)
    {

        for (y = 0; y < n - x; y++)
        {

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

            }

        }
    }
    fim = clock();

    //IMPRESSÃO DOS NÚMEROS
    for (x = 0; x < n; x++){
        printf("%d\t",vetor[x]);


    }

    tempo_execucao = (double)(fim - inicio) / (((double)CLOCKS_PER_SEC)*1000);
    printf("\n\nTempo de execução do programa: %lf",tempo_execucao);


    return 0;
}

Dei uma arrumada no código e agora parece que o loop está correto, mas o cálculo de tempo de execução as vezes da 0.00000 e outras da uma variada tipo 0.00001 e 0.000015. Creio eu que é um tempo muito pequeno para ordenação bubble sort.

devair1010 · 27 de fevereiro de 2018

@Esnack seu bublesort está funcionando certo, mas achei confuso o uso das variáveis do jeito que você colocou, acredito que seja mais fácil de entender desse modo aqui :

for(x=0;x<n;x++)
    for(y=x+1;y<n;y++)
        if(vetor[x] > vetor[y])
        {
            aux      = vetor[x];
            vetor[x] = vetor[y];
            vetor[y] = aux;
        }

Simon Viegas · 27 de fevereiro de 2018

Olá.

Apesar de não ser exatamente o foco do postagem, vou tentar complementar sobre o método de ordenação escolhido... vamos lá:

Em 26/02/2018 às 21:31, devair1010 disse:
@Esnack seu bublesort está funcionando certo, mas achei confuso o uso das variáveis do jeito que você colocou, acredito que seja mais fácil de entender desse modo aqui :
for(x=0;x<n;x++)
    for(y=x+1;y<n;y++)
        if(vetor[x] > vetor[y])
        {
            aux      = vetor[x];
            vetor[x] = vetor[y];
            vetor[y] = aux;
        }

@devair1010, apesar de popular, creio que esse código acima NÃO SEJA o Bubble Sort... veja, o Bubble Sort tem a seguinte característica:

Citação

O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

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

Então, a cada loop, uma bolha vai subindo a levando o menor entre as duas posições adjacentes... ou seja, a medida que vai subindo, vai deixando o elemento da direita maior... no final, a última posição vai ter o maior elemento.

Já no seu código, a cada loop, a comparação é feita sempre na mesma posição, ou seja, seria algo como: "a cada passagem fazer a última posição ter o maior elemento da sequência"... Seria como efetuar o algoritmo para encontra o "menor" valor para cada posição. Apesar do algoritmo ser mais simples, entendo que são coisas diferentes. Poderia também ser comparado ao "Selecion Sort", a diferença é que no "Selecion Sort" ele não fica trocando de posição, prefere primeiro achar a posição desejada ao final trocar.

Vamos tentar analisar o código do @Esnack:

    //BUBBLE SHOT
    for (x = 1; x < n; x++) { //aqui determina a quantidade de loops, ou seja, 'total-1", já que a primeira posição
                              // já estará ordenada quando terminar a segunda. Começa com 1 para facilitar o uso a seguir
        for (y = 0; y < n - x; y++) { //aqui determina até onde comparar a cada loop, ou seja, "do fundo do tanque até
                                      //uma posição anterior a posição que quer ordenar", pois a anterior vai comparar com
                                      //a próxima, que por consequencia será a últma. Se a última ficasse a esquerda, não existiria
                                      //uma posição depois para comparar OU iria comparar com uma posição que já está ordenada (perda de tempo)
            if (vetor[y] > vetor[y+1]) { //a bolha compara a posição atual com a próxima, para deixar o da direita maior, logo:
                                         //se posição atual menor que a posição posterior
                aux = vetor[y];          //então efetua a troca
                vetor [y] = vetor[y+1];
                vetor[y+1] = aux;
            }
        }
    }

Daí, o que pode existir são variações/melhorias, como em vez de fazer "total-1" vezes para o loop externo, poderia fazer até "enquanto houver trocas". Por ai vai.

RESUMINDO:
Teoricamente o código dele é um Bubble Sort.

Teoricamente o seu código é mais simples, e poderia ser utlizado, mas não poderia* chamar de Buubler Sort.

É como chamar chocolate branco de chocolate... pode ter a popularidade ou marketing que for, mas não é!!

Assim como tomate não é legume (é fruta);

Assim como caju não é fruta (a fruta é a castanha);

Assim como o Palmeiras não tem mundial..

Etc

No aguardo

phcmaster · 28 de fevereiro de 2018

Olá bom dia amigo, segue um código que fiz a algum tempo espero que ajude a dar uma clareada no que precisa. Lembrando que fiz como uma TAD.

----------------main.c----------------
  #include <stdio.h>
#include <stdlib.h>
#include "Ordenacao.h"

#define VET_TAM_MAX 100000
#define VET_TAM_MIN 10

int main()
{
    int vet_tam;
    do {
        printf("Informe tamanho do vetor [%d - %d]\n", VET_TAM_MIN, VET_TAM_MAX);
        scanf(" %d", &vet_tam);
    } while (vet_tam > VET_TAM_MAX || vet_tam < VET_TAM_MIN);

    printf("Criando vetor de %d posições...\n\n", vet_tam);
    int *vetor;
    vetor = cria_vetor(vet_tam);

    printf("**** VETOR ORIGINAL: ****\n");
    mostra_vetor(vetor, 0, vet_tam - 1);

    bubble_sort(vetor, vet_tam);

    printf("**** VETOR ORDENADO (Bubble): ****\n");
    mostra_vetor(vetor, 0, vet_tam - 1);

    return 0;
}

----------------Ordenacao.c----------------
  
  #include <stdlib.h>
#include <stdio.h>
#include "Ordenacao.h"

/*
 ****** Metodos auxiliares ******
 */
int* cria_vetor(int tam) {
     int *vet = (int *)calloc(tam, sizeof(int));
     int i;
     srand(time(0));
     for(i = 0; i < tam; i++){
	   vet[i] = rand()%(tam+200);
     }
     return vet;
}

void mostra_vetor(int vetor[], int ini, int fim) {
	int i;
	int tam = fim - ini + 1;
	int step = (tam / 100) + 1;
	char dots[5] = "";
	if (step > 1) {
        strcpy(dots, "... ");
	}
	printf("\n*** Vetor (inicio) ***\n");
	for(i = ini; i <= fim; i += step){
		printf("%d %s", vetor[i], dots);
	}
    printf("\n*** Vetor (fim) ***\n\n");
}

/* Bubble Sort */
void bubble_sort(int vetor[], int tamanho) {
    int n, swapped, i, aux;
    n = tamanho;
    do {
      swapped = 0;
      for (i = 1; i <= n-1; i++) {
         if (vetor[i-1] > vetor[i]) {
            aux = vetor[i-1];
            vetor[i-1] = vetor[i];
            vetor[i] = aux;
            swapped = i;
         }
      }
      n = swapped;
    } while (swapped != 0);
}

----------------Ordenacao.h----------------
  
 /*
 * Arquivo de definicao para biblioteca de métodos de ordenação
 */
#ifndef ORDENACAO_H
#define ORDENACAO_H

#include <time.h>

/*
 * Metodos de ordenacao
 */

/* Bubble Sort */
void bubble_sort(int vetor[], int tamanho);

/* Selection Sort */
void selection_sort(int vetor[], int tamanho);

/* Funções Auxiliares */
int* cria_vetor(int tam);
void mostra_vetor(int vetor[], int ini, int fim);

#endif

Esnack · 28 de fevereiro de 2018

Consegui arrumar o código, mas gostaria de saber se o tempo de execução está dentro do normal às vezes apresenta cerca de 2,00 ms outras vezes 3,00 ms está certo?

Citação

tempo_execucao = 1000*(double)(fim - inicio) / (double)CLOCKS_PER_SEC;

devair1010 · 1 de março de 2018

@Esnack testei aqui e também está mostrando esses mesmos valores, essa varição de tempo pode ser por causa da quantidade de números que são movimentados a cada execução do programa , pois depende dos números gerados, se caso tiver muitos números iguais então menos números são movidos e assim o tempo é menor, e para testar você pode colocar um

Sleep(1000);

no lugar desse código que você está testando, e ele vai mostrar que demorou 1000 ms, assim vemos que o cálculo está certo .

e essa linha do cálculo pode ser reduzida e ficaria assim :

tempo_execucao = (fim - inicio)*1000.0 / CLOCKS_PER_SEC;
printf("\n\nTempo de execução do programa: %.lf ms",tempo_execucao);

Simon Viegas · 1 de março de 2018

Olá.

Por uma coincidência da vida, um canal de que sigo (que por sinal não é nem de programação em si) postou um vídeo sobre "Métodos de Ordenação". Para quem quiser, vale a pena dar uma conferida no vídeo completo!!

Vejam como se comporta um Bubble Sort.

Obs. 1: só não entendi porque pega de 6 em 6 linhas... pelo algoritmo "padrão", acho que deveria ser de 2 em 2... mas em fim.... acho que demonstra bem o que quis dizer sobre o que entendo desse método... observem que a ideia é que essa faixa vermelha seria a bolha.. que vai "levando para sua direita" o maior termo a medida que avança... no final de cada ciclo as últimas posição ficam ordenadas.

Para esse código:

Em 26/02/2018 às 21:31, devair1010 disse:


for(x=0;x<n;x++)
    for(y=x+1;y<n;y++)
        if(vetor[x] > vetor[y])
        {
            aux      = vetor[x];
            vetor[x] = vetor[y];
            vetor[y] = aux;
        }

..que é mais popular, a cada loop, a linha que representa a posição x, já fica na ~~última~~ primeira posição não ordenada, e a linha que representa o y, ~~vai navegando até uma posição antes~~ começa da posição posterior ao x até a última posição, ou seja, as trocas são feitas diretamente na posição que quer ordenar... é parecido, mas é diferente, rs.

obs. 2: não sei qual método é mais eficiente, ou quais as diferenças na prática... mas é fato que esse acima é bem mais simples e fácil de entender... apenas estou tentando reforça que está fugindo um pouco da definição que entedi do Bubble Sort, ou seja, apesar de popularmente ser conhecido como Bubble Sort, ele seria outra coisa.

obs. 3: como tentado descrever acima, esse código está ordenando do início para o fim, ou seja, vai ficando em ordem da esquerda para direita... (a "bolha" está navegando no sentido oposto a posição que quer ordenar). O "ponteiro da posição" fica indo e voltando.

obs. 4: acho eu que o Bubble Sort lá do vídeo tenta usar a característica de manter as verificações em posições próximas. Desta forma, diminuindo um pouco o custo de chegar as posições, ou seja, tende a ser menos custoso ir de uma posição ao lado do que uma posição mais afastada... num estrutura, por exemplo, de uma lista encadeada, para ir da 1ª a 10ª posição, o computador precisa ir pulando de casa em casa, ou seja, do 1 para 2, do 2 para 3... daí precisaria dar muito mais saltos.

O que acham?

Att