Jump to content
silentvictor

Vetor de 500.000 posições em bubble sort

Recommended Posts

silentvictor

Bem, como trabalho da faculdade, me foi pedido para criar um programa com um vetor de 500.000 posições e que fosse preenchido com valores aleatórios de 0 a 5.000.000

Após isso foi pedido para que eu implementasse 3 tipos de funções de ordenação, bubble sort, selection sort e insert sort

Até agora conseui fazer ele povoar o vetor e o bubble sort, porem, quando faço ele rodar ele demora muito tempo, muito mesmo, deixei ele rodando por 10 minutos e ele não conseguiu imprimir a lista para que eu possa checar... Mas com valores menores como um vetor de 10000 ele consegue imprimir corretamente...

Queria saber se é normal esse tempo tão grande para 500.000, vi que ela é a função que mais demora para processar, mas estranhei que passasse tanto tempo...

Código aqui:

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

//FUnção bubble sort
void bubblesort (int vet[]) {    
    int flag, i, aux;

    do {
    flag = 0;
    for (i = 0; i < (500000 - 1); i++) {

/* Verfica se o vetor está em ordem, no caso ele coloca em ordem crescente, para decrescente trocar '>' por '<' */
if (vet[i] > vet[i+1]) {
    /* Caso não esteja, ordena */
    aux = vet[i];
    vet[i] = vet[i+1];
    vet[i+1] = aux;
    flag =1;
}
    }
    /* Repete enquanto algum valor estiver fora de ordem */
    } while (flag == 1);

    /* Imprime o vetor ordenado em ordem crescente */
    for (i = 0; i < 500000; i++) {
    printf ("%d ",vet[i]);
    }
    printf ("\n");
}

int main(int narg, char *argv[]){
int vet[500000], num;
int i;
srand( (unsigned)time(NULL) );
for(i=1 ; i <= 500000 ; i++)
{
vet[i]=rand() % 5000000;
}

bubblesort (vet);



return EXIT_SUCCESS;
}

Edited by thoga31
GeSHi

Share this post


Link to post
Share on other sites
HappyHippyHippo

não é estranho

o exercício é para tu teres a noção que existe processos que nem os computadores de hoje são capazes de resolver em 3 segundos, e por essa razão, inventaram maneiras mais eficientes para os resolver.

ps : recomendo comecares a usar o #define:

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

#define SIZE 500000

//Função bubble sort
void bubblesort (int vet[]) {   
 int flag, i, aux;

 do {
    flag = 0;
    for (i = 0; i < (SIZE - 1); i++) {
      /* Verfica se o vetor está em ordem, no caso ele coloca em ordem crescente, para decrescente trocar '>' por '<' */
      if (vet[i] > vet[i+1]) {
        /* Caso não esteja, ordena */
        aux = vet[i];
        vet[i] = vet[i+1];
        vet[i+1] = aux;
        flag =1;
     }
   }

   /* Repete enquanto algum valor estiver fora de ordem */
 } while (flag == 1);

 /* Imprime o vetor ordenado em ordem crescente */
 for (i = 0; i < SIZE; i++) {
   printf ("%d ",vet[i]);
 }
 printf ("\n");
}

int main(int narg, char *argv[]){
 int vet[size], num;
 int i;

 srand( (unsigned)time(NULL) );
 for(i=1 ; i <= SIZE ; i++) {
   vet[i]=rand() % SIZE;
 }

 bubblesort (vet);

 return EXIT_SUCCESS;
}

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
silentvictor

Que bem então :P

Fiquei com medo de ter feito besteira no código...

Estou começando a mexer com C agora, ainda não tenho muita noção de bibliotecas e de sintaxe .-.

Obrigado pela ajuda.

Se possivel, poderia deixar o tópico aberto? Creio que posso ter outras duvidas e para não abrir um outro tópico poderia postar nesse.

Edited by silentvictor

Share this post


Link to post
Share on other sites
pikax
Se possivel, poderia deixar o tópico aberto? Creio que posso ter outras duvidas e para não abrir um outro tópico poderia postar nesse.

Cria topicos para perguntas diferentes.


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Share this post


Link to post
Share on other sites
thoga31

Se possivel, poderia deixar o tópico aberto? Creio que posso ter outras duvidas e para não abrir um outro tópico poderia postar nesse.

Nenhum tópico é trancado, excepto se violar as regras.

Mais, como foi referido, para questões diferentes devem ser criados tópicos novos.


Knowledge is free!

Share this post


Link to post
Share on other sites
silentvictor

Terminei o algoritmo todinho, coloquei as 3 funções, mas na hora de calcular o tempo da função "insertion" ele sempre fica como 0 :c

Já alterei de todas as formas que sabia e o erro continua =/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 5000
//FUnção bubble sort
void bubblesort (int vet[]) {     
    int flag, i, aux; 

    do {
      flag = 0;
      for (i = 0; i < (SIZE - 1); i++) {

   /* Verfica se o vetor está em ordem, no caso ele coloca em ordem crescente, para decrescente trocar '>' por '<' */
   if (vet[i] > vet[i+1]) {
     /* Caso não esteja, ordena */
     aux = vet[i];
     vet[i] = vet[i+1];
     vet[i+1] = aux;
     flag =1;
   }
      }
    /* Repete enquanto algum valor estiver fora de ordem */ 
    } while (flag == 1);
  }
void insertion(int vet[])
{              
  int i, aux;

  for(i = 1; i < SIZE; i++)
  {
   while((i != 0) && (vet[i] < vet[i - 1])) {

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

}


void selection_sort(int vet[])
{
 int i, j, min, swap;
 for (i = 0; i < (SIZE-1); i++)
 {
  min = i;
  for (j = (i+1); j < SIZE; j++)
  {
   if(vet[j] < vet[min])
   {
    min = j;
         }
      }
  if (i != min)
  {
         swap = vet[i];
         vet[i] = vet[min];
         vet[min] = swap;
  }
 }

}

int main(int narg, char *argv[]){

clock_t end,start;
int vet[size];
int i;
start=clock();
srand( (unsigned)time(NULL) );
for(i=1 ; i <=  SIZE ; i++)
{
 vet[i]=rand() % 5000000;
}

start=clock();
bubblesort (vet);
end=clock();
printf("Tempo gasto Bubble: %4.0f ms\n\n",1000*(double)(end-start)/(double)(CLOCKS_PER_SEC));

start=clock();
selection_sort(vet);
end=clock();
printf("Tempo gasto Selection: %4.0f ms\n\n",1000*(double)(end-start)/(double)(CLOCKS_PER_SEC));
start=clock();
insertion(vet);
end=clock();
printf("Tempo gasto Insertion: %4.0f ms\n\n",1000*(double)(end-start)/(double)(CLOCKS_PER_SEC));
printf("Start=%d\nEnd=%d\n",start,end);

return EXIT_SUCCESS;
}

Edited by thoga31
GeSHi

Share this post


Link to post
Share on other sites
thoga31

Já reparaste que tu mudas, por exemplo na função bubblesort, o argumento vet mas isso não se reflecte na variável que foi passada?

Por outras palavras, vet é uma cópia da array, e não uma referência à original.

Dica:

lista = bubblesort(lista);

Já estás a ver o que tens de fazer?

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

uma análise à implementação dos algoritmos indica que o problema nao é ai, porque estão bem escritos.

como disse, este tipo de problema é usado para se verificar a diferente "qualidade" dos algoritmos de ordenação. e para isso, existem várias coisas que faltam no teu código:

- um método mais fiável de calculo do tempo decorrido (a função clock não é propriamente correcta para calculo de tempos)

- efectuar várias execuções iguais e calcular a média dos resultados

- efectuar várias execuções para tamanhos de listas diferentes

- O TEU ERRO : ordenar sempre vectores desordenados e não vectores que acabaram de ser ordenados anteriormente

corre o seguinte código para teres a noção que o teu professor pretende que tenhas após o execíco:

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

#define MAX 5000000

#define SIZE_MIN   5000
#define SIZE_STEP  5000
#define SIZE_MAX  20000

#define CICLES 6

#define xorswap(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))

int nswap = 0;
int ncompare = 0;

int * vector_create(size_t size) {
   int * vector = NULL;
   int i = 0;

   if ((vector = malloc(sizeof(int) * size)) != NULL) {
       for(i = 0; i < size; i++)
           vector[i] = rand() % MAX;
   }

   return vector;
}

void vector_destroy(int ** vector) {
   if (vector != NULL) {
       free(*vector);
       *vector = NULL;
   }
}

struct timespec time_get(void) {
   struct timespec ts;

   clock_gettime(CLOCK_REALTIME, &ts);

   return ts;
}

double time_diff(struct timespec start, struct timespec end) {
   double diff = 0;

   diff += end.tv_sec - start.tv_sec - 1;
   diff += (1000000000 - (double)start.tv_nsec + (double)end.tv_nsec) / 1000000000;

   return diff;
}

void sort_bubble(int * vector, size_t size) {
   int flag = 1, i = 0;

   nswap = 0;
   ncompare = 0;

   while (flag) {
       flag = 0;

       for (i = 0; i < size - 1; i++) {
           ncompare++;
           if (vector[i] > vector[i + 1]) {
               nswap++;
               xorswap(vector[i], vector[i + 1]);
               flag = 1;
           }
       }
   }
}

void sort_insertion(int * vector, size_t size) {
   int i = 0;

   nswap = 0;
   ncompare = 0;

   for (i = 1; i < size; i++) {
       ncompare++;
       while (i != 0 && vector[i] < vector[i - 1]) {
           nswap++;
           xorswap(vector[i], vector[i - 1]);
           i--;
       }
   }
}

void sort_selection(int * vector, size_t size) {
   int i = 0, j = 0, min = 0;

   nswap = 0;
   ncompare = 0;

   for (i = 0; i < size - 1; i++) {
       min = i;

       for (j = i + 1; j < size; j++) {
           ncompare++;
           if (vector[j] < vector[min]) {
               min = j;
           }
       }

       if (i != min) {
           nswap++;
           xorswap(vector[i], vector[min]);
       }
   }
}

int main(void) {
   int * vector, size, cycle, cycles;
   struct timespec start, end;
   double sum;

   srand(time(NULL));

   for (size = SIZE_MIN; size <= SIZE_MAX; size += SIZE_STEP) {
       // BUBBLE SORT
       printf("\nBUBBLE SORT - %d cycles with %d elements\n", CICLES, size);

       for (cycle = 0, cycles = 0, sum = 0.0; cycle < CICLES; cycle++) {
           printf("%do cycle sorting of a vector with %d elements with the booble sort algorithm : ", cycle, size);

           if ((vector = vector_create(size)) != NULL) {

               start = time_get();
               sort_bubble(vector, size);
               end = time_get();
               vector_destroy(&vector);

               cycles++;
               sum += time_diff(start, end);

               printf("%lf seconds (num. swaps = %d, num. compares = %d)\n", time_diff(start, end), nswap, ncompare);
           } else {
               printf(" error allocating %d bytes of memory\n", (int) (size * sizeof(int)));
           }
       }

       printf("The sorting of a vector with %d elements took in average %lf seconds to sort with a booble sort algorithm\n", size, sum / cycles);

       // INSERTION SORT
       printf("\nINSERTION SORT - %d cycles with %d elements\n", CICLES, size);

       for (cycle = 0, cycles = 0, sum = 0.0; cycle < CICLES; cycle++) {
           printf("%do cycle sorting of a vector with %d elements with the insertion sort algorithm : ", cycle, size);

           if ((vector = vector_create(size)) != NULL) {

               start = time_get();
               sort_insertion(vector, size);
               end = time_get();
               vector_destroy(&vector);

               cycles++;
               sum += time_diff(start, end);

               printf("%lf seconds (num. swaps = %d, num. compares = %d)\n", time_diff(start, end), nswap, ncompare);
           } else {
               printf(" error allocating %d bytes of memory\n", (int) (size * sizeof(int)));
           }
       }

       printf("The sorting of a vector with %d elements took in average %lf seconds to sort with a insertion sort algorithm\n", size, sum / cycles);

       // SELECTION SORT
       printf("\nSELECTION SORT - %d cycles with %d elements\n", CICLES, size);

       for (cycle = 0, cycles = 0, sum = 0.0; cycle < CICLES; cycle++) {
           printf("%do cycle sorting of a vector with %d elements with the selection sort algorithm : ", cycle, size);

           if ((vector = vector_create(size)) != NULL) {

               start = time_get();
               sort_selection(vector, size);
               end = time_get();
               vector_destroy(&vector);

               cycles++;
               sum += time_diff(start, end);

               printf("%lf seconds (num. swaps = %d, num. compares = %d)\n", time_diff(start, end), nswap, ncompare);
           } else {
               printf(" error allocating %d bytes of memory\n", (int) (size * sizeof(int)));
           }
       }

       printf("The sorting of a vector with %d elements took in average %lf seconds to sort with a selection sort algorithm\n", size, sum / cycles);
   }

   return 0;
}

  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
eatg75

@HappyHippyHippo na tua implementacao nao seria melhor utilizar um array igual, i.e. um array com os mesmos

elementos nas mesmas posicoes, assim estariamos a comparar as diferentes implementacoes

algoritimos com um mesmo array e teriamos um resultado mais preciso.


Victarion seized the dusky woman by the wrist and pulled her to him.

Victarion - She will do it. Go pray to your red god. Light your fire, and tell me what you see.

Moqorro's dark eyes seemed to shine.

Moqorro - I see dragons.

Share this post


Link to post
Share on other sites
HappyHippyHippo

@HappyHippyHippo na tua implementacao nao seria melhor utilizar um array igual, i.e. um array com os mesmos

elementos nas mesmas posicoes, assim estariamos a comparar as diferentes implementacoes

algoritimos com um mesmo array e teriamos um resultado mais preciso.

imagina que na sua bela aleatoriedade, a criação/população do vector origina um vector já ordenado, puff, lá se foi o teste.

é por isso que se deve fazer vários testes com vectores diferentes para diluir qualquer tipo de tendência (seja de vector semi ordenado ou outra qualquer) e obter resultados mais próximos da média verdadeira.

Edited by HappyHippyHippo
  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Flinger

@Hyppo:

Código muito bem ordenado e estruturado, como de costume, mas tenho de concordar com o eatg75. Como tu dizes, um dos vectores pode sair ordenado, o que vai dar a impressão que aquele algoritmo é melhor que os outros, que tiveram arrays desordenados. Para mim, deveriam todos usar o mesmo array, mas, para melhorar a comparação, usar várias amostras em vez de apenas uma.

PS: Por outro lado, a quantidade de amostras que fazes para cada um vai diluir bastante qualquer aleatoriedade, e os resultados vão acabar por reflectir de qualquer forma a eficiência dos algoritmos.

Já agora, porque é que no clock_gettime usas o CLOCK_REALTIME e não o MONOTONIC?

Edited by Rui Carlos

Share this post


Link to post
Share on other sites
HappyHippyHippo

@Hyppo:

Código muito bem ordenado e estruturado, como de costume, mas tenho de concordar com o eatg75. Como tu dizes, um dos vectores pode sair ordenado, o que vai dar a impressão que aquele algoritmo é melhor que os outros, que tiveram arrays desordenados. Para mim, deveriam todos usar o mesmo array, mas, para melhorar a comparação, usar várias amostras em vez de apenas uma.

PS: Por outro lado, a quantidade de amostras que fazes para cada um vai diluir bastante qualquer aleatoriedade, e os resultados vão acabar por reflectir de qualquer forma a eficiência dos algoritmos.

eu uso várias amostras, nota que para cada combinação algoritmo/tamanho do vector é feito CICLES vezes.

eu compreendo a ideia de usar os mesmos vectores para a comparação.

é verdade que o valor relativo entre os tempos de execução dos algoritmos é mais realista, no entanto existe um valor que fica distorcido em todos os testes : o tempo real de execução.

imagina que executo 10 ciclos em cada algoritmo onde em cada ciclo é um vector diferente (mas igual entre algorimtos). ao existir um vector semi-ordenado na lista de 10 vectores, terei em todos os algorimos um valor que puxa a média verdadeira para um valor distânte da média real.

no meu caso, ao usar vectores distintos entre algoritmos, a existência do vector semi-ordenado irá afectar o resultado de somente um algoritmo.

no entanto, existe uma ferramenta na estatística que serve para culmatar tanto um caso como o outro, a variãncia.

bastaria calcular a variância no meu método para determinar que o um dos algorimtos contemplou um ou mais casos "não padrão", enquanto que no vosso caso, é variância aumenta para todos os algoritmos.

alem disso, como é de reconhecimento mútuo, ao aumentar o número de amostras, a anormalidade é diluida.

no final, como acabei de provar, é indiferente um caso ou outro bastando usar as ferramentas matemáticas disponíveis para analisar os resultados obtidos.

Já agora, porque é que no clock_gettime usas o CLOCK_REALTIME e não o MONOTONIC?

simplesmente usei-o por ter sido copy-paste de um outro trabalho.

é certo que neste caso o CLOCK_MONOTONIC sera o mais apropriado, mas como só existe problemas no uso do CLOCK_REALTIME nos dias onde a hora muda, e durante essa mesma hora ... no final funciona bem.


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Flinger

simplesmente usei-o por ter sido copy-paste de um outro trabalho.

é certo que neste caso o CLOCK_MONOTONIC sera o mais apropriado, mas como só existe problemas no uso do CLOCK_REALTIME nos dias onde a hora muda, e durante essa mesma hora ... no final funciona bem.

Não é bem assim. O CLOCK_REALTIME pode ser afectado por um serviço NTP, que pode efectuar correcções à hora devido a variações da frequência de relógio do sistema, ao passo que o CLOCK_MONOTONIC não é afectado. Embora estas alterações sejam pequenas podem influenciar o resultado final, mais uma vez, sendo essa diferença diluida com o número de testes efectuados.

Enfim, fica só o aparte.

Edited by Flinger

Share this post


Link to post
Share on other sites
HappyHippyHippo

Não é bem assim. O CLOCK_REALTIME pode ser afectado por um serviço NTP, que pode efectuar correcções à hora devido a variações da frequência de relógio do sistema, ao passo que o CLOCK_MONOTONIC não é afectado. Embora estas alterações sejam pequenas podem influenciar o resultado final, mais uma vez, sendo essa diferença diluida com o número de testes efectuados.

Enfim, fica só o aparte.

é preciso ter a noção de escala e frequência do processo.

http://www.ntp.org/ntpfaq/NTP-s-algo.htm#Q-ALGO-CLK-UPD

If adjtime() is used, ntpd will update the system clock every second. If ntp_adjtime() is available, the operating system can compensate clock errors automatically, requiring only infrequent updates.

...

ntpdc> loopinfo

offset: -0.000102 s

frequency: 16.795 ppm

poll adjust: 6

watchdog timer: 63 s

como podes ver, a relação quantidade de ajuste/frequência é irrelaveante quando temos testes com resultados com valores mínimos de 0.5 segundos

mas novamente digo, sim, o melhor seria usar o CLOCK_MONOTONIC (ou o mais recente CLOCK_MONOTONIC_RAW)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
motherFFH

Esse programa está muito bom :-)

Só sugeria duas coisas:

1. evitar aportuguesar os termos em inglês: CICLES -> CYCLES

2. o main devia ter os algoritmos em tabela para evitar a repetição do bloco de testes

e.g

#define array_size(x) sizeof(x)/sizeof(x[0])

int main(void) {
int * vector, size, cycle, cycles;
struct timespec start, end;
double sum;

struct {
	char *algo_name;
	void (*algo_function)(int * vector, size_t size);
} algo_table[] = {
	{"bubble sort", sort_bubble},
	{"insertion sort", sort_insertion},
	{"selection sort", sort_selection},
};

srand(time(NULL));

for (size = SIZE_MIN; size <= SIZE_MAX; size += SIZE_STEP) {
	int i,n;
	for (i=0, n=array_size(algo_table); i<n; i++) {
		char *algo_name = algo_table[i].algo_name;
		void (*algo_function)(int *, size_t) = algo_table[i].algo_function;

		printf("\n%s - %d cycles with %d elements\n", algo_name, CICLES, size); /* toupper(algo_name) */

		for (cycle = 0, cycles = 0, sum = 0.0; cycle < CICLES; cycle++) {
			printf("%do cycle sorting of a vector with %d elements with the %s algorithm : ", cycle, size, algo_name);

			if ((vector = vector_create(size)) != NULL) {

				start = time_get();
				algo_function(vector, size);
				end = time_get();
				vector_destroy(&vector);

				cycles++;
				sum += time_diff(start, end);

				printf("%lf seconds (num. swaps = %d, num. compares = %d)\n", time_diff(start, end), nswap, ncompare);
			} else {
				printf(" error allocating %d bytes of memory\n", (int) (size * sizeof(int)));
			}
		}

		printf("The sorting of a vector with %d elements took in average %lf seconds to sort with a %s algorithm\n", size, sum / cycles, algo_name);
	}
}

return 0;
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.