Publicidade cabeçário

sexta-feira, 24 de maio de 2013

Estrutura de Dados - Ordenação e Busca

Ordenação Selection Sort

O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Descrição do Algoritmo:
  •  Procurar menor elemento e trocar com o elemento da 1º posição;
  •  Procurar 2º menor elemento e trocar com o elemento na 2º posição,proceder assim até a ordenação estar completa.
Exemplo de ordenação Selection Sort
Exemplo de ordenação Selection Sort
fonte da imagem: bdfatec.blogspot.com.br

Ordenação pelo método Bubble Sort

Por ser simples e de entendimento e implementação fáceis, o Bubblesort (bolha) está entre os mais conhecidos e difundidos métodos de ordenação de arranjos. Mas não se trata de um algoritmo eficiente, é estudado para fins de desenvolvimento de raciocínio.

O princípio do Bubblesort é a troca de valores entre posições consecutivas, fazendo com que os valores mais altos ( ou mais baixos ) "borbulhem" para o final do arranjo (daí o nome Bubblesort). Diferente do selection sort que "joga" para o inicio os menores valores ou para trás dependendo do caso.  
Exemplo de ordenação Bubble Sort
Exemplo de ordenação Bubble Sort
fonte da imagem: bdfatec.blogspot.com.br

Busca Linear Sequencial


Método de pesquisa mais simples: a partir do primeiro registro, pesquise seqüencialmente até encontrar a chave procurada; então pare. 

• Armazenamento de um conjunto de registros por meio de um array.Pesquisa Sequencial
• A Busca (find): 
Pesquisa retorna o índice do registro que contém a chave x
• Caso não esteja presente, o valor retornado é -1. 
A implementação não suporta mais de um registro com uma mesma chave, pois retorna o primeiro encontrado

Definição do algoritmo 

  • Percorrer o vetor desde a primeira posição até a última. 
  • Para cada posição i, comparamos vetor[i] com valor.
  • Se forem iguais dizemos que valor existe.
  • Se chegarmos ao fim do vetor sem sucesso dizemos que o valor não existe!

Busca Binária

Pesquisa em tabela pode ser mais eficiente se registros forem mantidos em ordem. Para saber se uma chave está presente na tabela:

  • Compare a chave com o registro que está na posição do meio da tabela. 
  • Se a chave é menor então o registro procurado está na primeira metade da tabela
  • Se a chave é maior então o registro procurado está na segunda metade da tabela.
  • Repita até que a chave seja encontrada ou que se constate que a chave não existe na tabela.

Definição do algoritmo 

  • Se o elemento procurado e o elemento comparado;
  • Se ele está antes do elemento comparado ou; se está depois.
  • Se fi zermos isso sempre com o elemento do meio da lista, a cada comparação dividiremos a lista em duas, reduzindo nosso tempo de busca.
  • Se em um determinado momento o vetor, após sucessivas divisões, tiver tamanho zero, então o elemento não está no vetor.

Programa

O programa proposto foi o seguinte: 
  1. Criar uma Selection sort
  2. Criar um Bubble sort
  3. Ordenar em ordem Decrescente
  4. Busca Sequencial
  5. Busca Binária
  6. Imprimir valores em tela
  7. Inserir valores no vetor
Menu com ordenação e busca de valores
Menu com ordenação e busca de valores
fonte da imagem: bdfatec.blogspot.com.br
Certo vamos ao programa. Primeiramente vamos colocar os métodos e as bibliotecas


#include <stdio.h>
#include <conio.h>
#include <windows.h>

/*****************************Busca Binaria*************************************/
void buscabinaria(int *v, int tamanho){
       int esq=0,dir=tamanho,chave,meio;
       
       printf("\n\tDigite o valor a ser pesquisado\n\t");
       scanf("%d",&chave); 
       
       while(esq<=dir){
        meio = (esq + dir)/2; //aqui definimos exatamente o meio da lista
        
        if(v[meio]<chave){
           esq = meio + 1;               
           }else if(v[meio]> chave){
                 dir = meio - 1;
                 }else{
                 printf("\n\t valor %d : indice %d\n\t",chave,meio);
                 printf("\n\t ******* Item encontrado com sucesso ******");
                 break;
                 }//fim if
//a ideia aqui é aproximar cada vez mais do quadrante do número a ser pesquisado
         }//fim while         
      if(chave != meio)printf("\n\t ***** Valor inexistente ******");
//condicional utilizada quando não existe o número buscado
     }// fim buscabinaria

/*****************************Busca Linear*************************************/
void buscalinear(int *v, int tamanho){
       int cont,chave;
       
       printf("\n\tDigite o valor a ser buscado\n\t");
       scanf("%d",&chave); 
       
       for(cont=0;cont<tamanho;cont++){
         if(chave == v[cont]){
           printf("\n\tValor %d : Indice %d",chave,cont);
           printf("\n\t ******* Item encontrado com sucesso ******");
           break;
                  }     
//aqui a ideia é percorrer o vetor inteiro até encontrar o número a ser pesquisado               
       }//fim for 
       if(cont == tamanho) printf("\n\t ***** Valor inexistente ******");
//condicional utilizada quando não existe o número buscado
     }// fim buscalinear
   
/*****************************Decrescente**************************************/
void decrescente(int *v, int tamanho){
     int aux;
     for(int a=0;a<tamanho;a++){
         for(int b=tamanho-1;b>0;b--){
           if(v[b-1]<v[b]){
             aux = v[b];
             v[b] = v[b-1];
             v[b-1] = aux;
                             }//fim if
                            }//fim for
                          }//fim for
//aqui cada valor é confrontado com os demais em um turno e "jogado" pra trás quando for menor
     printf("\n\t ******* Colocado em ordem Decrescente com sucesso ******");
     
     }// fim decrescente
/*****************************Bolha********************************************/
void bolha(int *v, int tamanho){
     int aux;
     for(int a=0;a<tamanho;a++){
         for(int b=tamanho-1;b>0;b--){
           if(v[b-1]>v[b]){
             aux = v[b];
             v[b] = v[b-1];
             v[b-1] = aux;
                             }//fim if
                            }//fim for
                          }//fim for
//aqui cada valor é confrontado com os demais em um turno e "jogado" pra trás quando for maior
     printf("\n\t ******* Ordenado pelo Método Bolha com sucesso ******");
     }// fim bolha
     
/*****************************selection sort***********************************/
void selectionsort(int *v, int tamanho){
     int troca,aux,menor,cont1,cont2,indice = 0;
       
       for(cont1=0;cont1<tamanho;cont1++){
          troca = 0;
          menor = v[cont1];
          for(cont2=cont1+1;cont2<tamanho;cont2++){
              if(v[cont2]< menor){
              troca = 1;
              menor = v[cont2];      
              indice = cont2;       
              }//fim if                  
           }//fim for                 
       
                if(troca == 1){
                 aux = v[cont1];
                 v[cont1] = menor;
                 v[indice] = aux;     
                 }//fim if
       }//fim for
//aqui os valores são confrontados e trocam de lugar
     printf("\n\t ******* Ordenado pelo Selection Sort com sucesso ******");
     }//fim selectionsort
     
/*********************************imprimir*************************************/
void imprime(int *v,int tamanho){
     for(int iCont = 0; iCont<tamanho;iCont++) printf("\n\t %d elemento = %d",iCont+1,v[iCont]);
     printf("\n\t ******* Impresso com sucesso! ******");
     }//fim imprime

Agora vamos colocar o menu do programa com o main, onde iremos chamar os métodos.


int main(){
    int vet[100];
    int nOpc,iCont=0,iTamanho=0; 
    bool order = false;
do{
printf("----------------------- Menu --------------------------------");
printf("\n\n\t1 - Inserir valor no vetor");
printf("\n\t2 - Imprime vetor");
printf("\n\t3 - Ordenar: Selection Sort");
printf("\n\t4 - Ordenar: Metodo Bolha");
printf("\n\t5 - Ordenar Decrescente");
printf("\n\t6 - Busca Sequencial");
printf("\n\t7 - Busca Binaria");
printf("\n\t0 - Sair");
printf("\n\nDigite a opcao desejada: ");
scanf("%d",&nOpc);
switch (nOpc){
case 0:
                 printf("\n\nObrigado por utilizar o programa\n\n Pressione ENTER para sair...");
                 break;
            case 1:
printf("\n\nDigite o valor desejado: ");
scanf("%d",&vet[iCont]);iTamanho++;iCont++;
printf("\n\nPressione ENTER para continuar...\n\n");
break;
case 2:
                 if(iCont != 0){
        imprime(&vet[0],iTamanho);/*a manha é enviar para o método a posição inicial do vetor utilizando o &(ecomercial)*/
                 }else printf("\n\t Insira valores primeiro");
printf("\n\nPressione ENTER para continuar...\n\n");
break;
//aqui fizemos um teste para somente ordenar se ao menos um item foi inserido
            case 3:
                 if(iCont != 0){
                 selectionsort(&vet[0],iTamanho);
                 order = true; //indica que o vetor foi ordenado
                 }else printf("\n\t Insira valores primeiro");
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
//aqui fizemos um teste para somente ordenar se ao menos um item foi inserido
            case 4:
                 if(iCont != 0){
                 bolha(&vet[0],iTamanho);
                 order = true; //indica que o vetor foi ordenado
                 }else printf("\n\t Insira valores primeiro");
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            case 5:
                 if(order == true){
                 decrescente(&vet[0],iTamanho);   
                          }else{
                           printf("\n\t Ordene o vetor primeiro");
                           printf("\n\t Utilize item 2 ou item 3");
                                }
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
/*testamos se o vetor tem valores e se está ordenado para depois colocá-lo em ordem decrescente*/
            case 6:
                 if(iCont != 0){
                 buscalinear(&vet[0],iTamanho);
                 }else printf("\n\t Insira valores primeiro");
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
//aqui fizemos um teste para somente ordenar se ao menos um item foi inserido
            case 7:
                 if(iCont != 0 && order == true){
                 buscabinaria(&vet[0],iTamanho);
                 }else printf("\n\t Insira Valores e/ou Ordene o vetor primeiro");
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
/*testamos se o vetor tem valores e se está ordenado já que a busca binária necessita disso*/
            default:
                printf("\n\nOpcao Invalida \n");  
                break;  
//valor padrão caso seja digitado algum número que o menu não possua
} // fim switch
getch();
system("cls");
       }while(nOpc != 0);
    }//fim main

Bom é isso pessoal. Bons estudos, qualquer dúvida me pergunte ou manda um comentário... Abraço a todos! by Chuck
fonte: < Sistemas de Informação prof. Regis Selection Sort >
            < Algoritmo de Ordenação - Selection Sort
            < Bubble Sort
            < MC-102 | Aula 15 Busca sequencial e bin
            < Pesquisa Sequencial e Binária  Prof. Túlio Toffolo >

Gostou do blog? Então segue =D 
Gostou da postagem? Então comenta ;DDD 
Fique por dentro das atualizações