Testar o melhor método de organização C (inserção, bolha e shell-sort)

Publicado por Edmar Wantuil (última atualização em 25/10/2011)

[ Hits: 9.150 ]

Homepage: wantuil.com

Download pesquisa.c




Fiz esse código para testar qual é o melhor método de organização entre:

* método de inserção
* método bolha
* método shell-sort

O código cria um vetor com 100.000 números aleatórios e os ordena usando os 3 métodos, ao término ele fala o tempo de cada um.

  



Esconder código-fonte

/*
  Feito por: Edmar Wantuil Silva Júnior
  Em 21/10/2011
  O código popula um vetor com 100000 numeros aleatorios e tenta 3 formas de ordenação diferentes:
    * Organização pelo metodo de inserção
    * Organização pelo metodo bolha
    * Organização pelo metodo shell-sort
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define tamanho 100000

int vetor[tamanho];
int atual= 0;
int proce= 0;

//Variaveis para a contagem do tempo
clock_t comeco,fim;
double tm_inse,tm_bolh,tm_shel;
void limpar_tela()
{
  system("clear");
}

//Essa função verifica se o numero já existe no vetor
bool livre(int procurado)
{
  int cont= 0;
  while(atual > cont)
  {
    if(vetor[cont] == procurado)
      return false;
    cont++;
  }
  return true;
}


//Essa função mostra uma barra de progresso na tela
void processo(int act, float x, float y)
{
  double percetagem= x / y * 100;
  if((percetagem > proce) && (100 > proce))
  {
    limpar_tela();
    if((percetagem > proce) && (100 > proce))
      proce+= 2;
    switch(act)
    {
      case 1:
        printf("Adicionando!\n");
      break;
      case 2:
        printf("Organizando por insercao!\n");
      break;
      case 3:
        printf("Organizando por bolha!\n");
      break;
      case 4:
        printf("Organizando por shell-sort!");
      break;
    }
    printf("                         %d/100\n", proce);
    printf("----------------------------------------------------\n");
    printf("|");
    int cont= 0;
    while((proce / 2) > cont)
    {
      printf("#");
      cont++;
    }
    float cont2= proce - 100;
    while(0 > cont2 / 2)
    {
      printf(" ");
      cont2+=2;
    }
    printf("|\n");
    printf("----------------------------------------------------\n");
    printf("     Aguarde...\n");
  }
}

//organiza pelo metodo de inserção
void insercao()
{
  comeco= clock();
  int cont= 0;
  int temp= 0;
  while(tamanho > cont)
  {
    processo(2, (cont + 1), tamanho);
    temp= vetor[cont];
    int cont2= cont - 1;
    while((cont2 >= 0) && (vetor[cont2] > temp))
    {
      vetor[cont2 + 1]= vetor[cont2];
      cont2--;
    }
    vetor[cont2 + 1]= temp;
    cont++;
  }
  fim= clock();
  tm_inse=(fim-comeco)/CLOCKS_PER_SEC;
}

//Organiza pelo metodo bolha
void bolha()
{
  comeco= clock();
  int n= atual;
  float aux;
  int i, passo= 1;
  int cont= 0;
  bool trocar= true;
  do
  {
    cont++;
    trocar= false;
    for(i= 0; i < n - passo; i++)
    {
      processo(3, (cont + 1), (tamanho * 0.95));
      if(vetor[i] > vetor[i + 1])
      {
        trocar= true;
        aux= vetor[i];
        vetor[i]= vetor[i + 1];
        vetor[i + 1]= aux;
      }
    }
    passo++;
  }
  while(trocar);
  fim= clock();
  tm_bolh=(fim-comeco)/CLOCKS_PER_SEC;
}

//organiza pelo metodo shell-sort
void shell()
{
  comeco= clock();
  int aux;
  int n= tamanho;
  int i, j, h;  
  h = n;
  int cont= 0;
  do
  {
    h = h / 2;
    for (i = h; i < n; i++ )
    {
      j = i;
      aux = vetor[i];
      while ( ( j >= h ) && ( vetor[j-h] > aux ) )
      {
        cont++;
        processo(4, (cont + 1), 278000);
         vetor[j] = vetor[j-h];
         j = j - h;
      }
      vetor[j] = aux;
    }
  } while (h > 1 );
  fim= clock();
  tm_shel=(fim-comeco)/CLOCKS_PER_SEC;
}

//A função popula o vetor com numeros aleatorios sem repetir os numeros
int popula()
{
  while(tamanho > atual)
  {
    int temp= rand() % 1000000;
    while(livre(temp) == false)
    {
      temp= rand() % 1000000;
    }
    vetor[atual]= temp;
    processo(1, (atual + 1), tamanho);
    atual++;
  }
}

//Exibi o tempo
void tempo()
{
  limpar_tela();
  printf("Insercao: %.0f segundos\n",tm_inse);
  printf("Bolha: %.0f segundos\n",tm_bolh);
  printf("Shell-Sort: %.0f segundos\n",tm_shel);
}

//Função principal
int main()
{
  popula();
  proce= 0;
  insercao();
  atual= 0;
  proce= 0;
  popula();
  proce= 0;
  bolha();
  atual= 0;
  proce= 0;
  popula();
  proce= 0;
  tempo();
  return 0;
}

Scripts recomendados

Comando strieql

Quadrado Mágico

gotoxy() no Linux

Múltiplos de bit e byte

Sequencia Fibonacci


  

Comentários
[1] Comentário enviado por wantuiliv em 12/11/2011 - 13:21h

Peso desculpas a todas as pessoas que viram esse meu código, ele tem o seguinte erro, deve se acrescentar shell(); entre proce= 0; e tempo();
Por favor me perdoem me faltou atenção.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor HostGator.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Viva o Android

Tópicos

Top 10 do mês

Scripts