Analize dos métodos de ordenação

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Analize dos métodos de ordenação

Mensagem  Renancr em Dom 14 Ago 2011 - 17:06

Analize dos métodos de ordenação


Para as versões de método Bubble Sorte, Insertion Sort, e Selection Sort, avalie as seguintes questões:

Como os métodos irão se comportar no melhor e no pior caso, independente do tamanho do vetor;

  • Numero de comparações.

  • Numero de posições visitadas.


Bubble Sort - versão 1
Código:
void bubble_v1(int vetor[])
{
   int n, i, aux;

   for(n=1; n <= tam; n++)
   {
      for(i=0; i < (tam-1); i++)
      {
         if(vetor[i] > vetor[i+1])
         {
            aux = vetor[i];
            vetor[i] = vetor[i+1];
            vetor[i+1] = vetor[i];
         }
      }
   }
}

Bubble Sort - versão 2
Código:
int bubble_v2(int vetor[])
{
   int j, i, aux;

   for(j=1; j < tam; j++)
      for(i=(tam-1); i >= j; i--)
      {
         if(vetor[i] < vetor[i-1])
         {
            aux = vetor[i];
            vetor[i] = vetor[i-1];
            vetor[i-1] = aux;
         }
      }
}

Bubble Sort - versão 3
Código:
void bubble_sort(int vet[])
{
   int n=1, troca=1, i, aux;

   while(n<=tam && troca == 1)
   {
      troca=0;
      for(i=0; i<=3; i++)
         if(vet[i] < vet[i+1])
         {
            troca=1;
            aux = vet[i];
            vet[i] = vet[i+1];
            vet[i+1] = aux;
         }
         n++;
   }
}


Última edição por Renancr em Dom 21 Ago 2011 - 18:56, editado 4 vez(es)
avatar
Renancr

Mensagens : 118
Data de inscrição : 08/03/2010

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Re: Analize dos métodos de ordenação

Mensagem  Renancr em Dom 21 Ago 2011 - 18:09

Código:
#include <iostream>
using namespace std;

//definição do tamanho do vetor
const int tam=5;

void cria_vet(int vet1[], int vet2[], int vet3[]);
int bubble_v1(int vetor[tam], int pv[tam]);
int bubble_v2(int vetor[tam], int pv[tam]);
int bubble_v3(int vetor[tam], int pv[tam]);


void main()
{
  int i, mc[tam], pc[tam], troca, pv[tam];

  cria_vet(mc, pc, pv);
  cout<< "Melhor Caso\n";
  for(i=0; i<tam; i++)
     cout<< mc[i] << " ";
  cout<< "\nPior Caso\n";
  for(i=0; i<tam; i++)
     cout<< pc[i] << " ";
  cout<< "\n\n";

  cout<< "================================\n";
  cout<< "\tBubble V1\n";
  cout<< "================================\n";
  troca=0;
  troca=bubble_v1(mc, pv);
  cout<< "Numero de trocas, no melhor caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no melhor caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n\n";
  for(i=0; i < tam; i++)
      pv[i]=0;
  troca=bubble_v1(pc, pv);
  cout<< "Numero de trocas, no pior caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no pior caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n================================\n\n";
  system("pause");
  cria_vet(mc, pc, pv);
  cout<< "================================\n";
  cout<< "\tBubble V2\n";
  cout<< "================================\n";
  troca=0;
  troca=bubble_v2(mc, pv);
  cout<< "Numero de trocas, no melhor caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no melhor caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n\n";
  for(i=0; i < tam; i++)
      pv[i]=0;
  troca=bubble_v2(pc, pv);
  cout<< "Numero de trocas, no pior caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no pior caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n================================\n\n";
  system("pause");
  cria_vet(mc, pc, pv);
  cout<< "================================\n";
  cout<< "\tBubble V3\n";
  cout<< "================================\n";
  troca=0;
  troca=bubble_v3(mc, pv);
  cout<< "Numero de trocas, no melhor caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no melhor caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n\n";
  for(i=0; i < tam; i++)
      pv[i]=0;
  troca=bubble_v3(pc, pv);
  cout<< "Numero de trocas, no pior caso: " << troca << "\n";
  cout<< "Posicoes Visitadas, no pior caso:\n";
  for(i=0; i <tam; i++)
  {
      cout<< "P:" << i << " ";
      cout<< "Q:" << pv[i] << " ";
  }
  cout<< "\n================================\n\n";
  system("pause");
}

void cria_vet(int vet1[], int vet2[], int vet3[])
{
  int i, x;
  x=(tam - 1);
  for (i = 0; i < tam; i++)
  {
      vet1[i] = i;
      vet2[x]= i;
      x--;
      vet3[i] = 0;
  }
}

int bubble_v1(int vetor[tam], int pv[tam])
{
  int n, i, aux, troca=0;

  for(n=1; n <= tam; n++)
  {
      for(i=0; i < (tam-1); i++)
      {
        pv[i]+=1;
        pv[i+1]+=1;
        if(vetor[i] > vetor[i+1])
        {
            troca++;
            aux = vetor[i];
            vetor[i] = vetor[i+1];
            vetor[i+1] = vetor[i];
            pv[i]+=1;
            pv[i+1]+=1;
        }
      }
  }
  return troca;
}

int bubble_v2(int vetor[tam], int pv[tam])
{
  int j, i, aux, troca=0;

  for(j=1; j < tam; j++)
      for(i=(tam-1); i >= j; i--)
      {
        pv[i]+=1;
        pv[i-1]+=1;
        if(vetor[i] < vetor[i-1])
        {
            troca++;
            aux = vetor[i];
            vetor[i] = vetor[i-1];
            vetor[i-1] = aux;
            pv[i]+=1;
            pv[i-1]+=1;
        }
      }
  return troca;
}

int bubble_v3(int vetor[tam], int pv[tam])
{
  int n=1, i, aux, troca=1, swap=0;
  while(n < tam && troca == 1)
  {
     troca=0;
      for(i=0; i<=(tam-2); i++)
      {
        pv[i]+=1;
        pv[i+1]+=1;
        if(vetor[i] < vetor[i+1])
        {
            troca=1;
         swap++;
            aux= vetor[i];
            vetor[i]= vetor[i+1];
            vetor[i+1]= aux;
            pv[i]+=1;
            pv[i+1]+=1;
        }
        n++;
      }
  }
  return swap;
}
avatar
Renancr

Mensagens : 118
Data de inscrição : 08/03/2010

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum