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:
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 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
- 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 fizermos 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:
- Criar uma Selection sort
- Criar um Bubble sort
- Ordenar em ordem Decrescente
- Busca Sequencial
- Busca Binária
- Imprimir valores em tela
- Inserir valores no vetor
 |
| 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 >
< 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
Nenhum comentário:
Postar um comentário