Ordenando vetores usando Linguagem C Terminal de Informação

Prévia do material em texto

25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 1/9
Publicado por Dan_Atilio
Terminal de Informação
Aqui a informação se torna conhecimento!
Ordenando vetores usando Linguagem C
MAI 10
Olá pessoal…
Hoje irei falar de ordenação de vetores usando a linguagem C (Selection Sort – Método Seleção,
Inserction Sort – Método Inserção e Bubble Sort – Método de troca).
Primeiramente, porque usar uma ordenação? São várias as vantagens, como por exemplo, com os
valores ordenados, fica mais fácil, encontrar qual é o menor valor, qual é o maior valor, dentre
outras vantagens.
Alguns dos principais métodos são o de Seleção, Inserção e o de Troca (ou Flutuação, ou Bolha),
abaixo irei exemplificar cada um deles:
$> Método de Seleção (Selection Sort)
O método de seleção, consiste em uma ordenação básica, onde sempre o menor valor será passado
para o início do vetor (primeira posição), e depois o segundo menor valor para a segunda posição e
assim sucessivamente, ordenando os valores do vetor. Abaixo um exemplo em GIF:
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 2/9
 (http://terminaldeinformacao.files.wordpress.com/2013/05/ord_selecao.gif)
Método de Seleção
Trecho de código em Linguagem C, responsável pelo Selection Sort:
void selection_sort(int num[], int tam) 
{ 
 int i, j, min, swap; 
 for (i = 0; i < (tam-1); i++) 
 { 
 min = i; 
 for (j = (i+1); j < tam; j++) { 
 if(num[j] < num[min]) { 
 min = j; 
 } 
 } 
 if (i != min) { 
 swap = num[i]; 
 num[i] = num[min]; 
 num[min] = swap; 
 } 
 } 
}
$> Método de Inserção (Inserction Sort)
A ordenação por Inserção é um algoritmo simples, mas eficiente somente em vetores pequenos,
basicamente ele percorre um vetor da esquerda para a direita, e conforme avança, vai alinhando os
valores da sua esquerda.
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 3/9
(http://terminaldeinformacao.files.wordpress.com/2013/05/ord_insercao.gif)
Método de Inserção
Trecho de código em Linguagem C, responsável pelo Insercion Sort:
void insertionSort(int V[], int tam) 
{ 
 int i, j, aux; 
 for(i = 1; i < tam; i++){ 
 j = i; 
 while((j != 0) && (V[j] < V[j - 1])) { 
 aux = V[j]; 
 V[j] = V[j - 1]; 
 V[j - 1] = aux; 
 j--; 
 } 
 } 
}
$> Método de Troca (Bubble Sort, ou Método de Flutuação / Bolha)
O método de Troca, ou método Bolha, é um algoritmo de ordenação simples, sendo que a ideia é
percorrer o vetor várias vezes (geralmente com o número de elementos), e a cada vez, ‘flutuar’ o
maior elemento da sequência, ou seja, essa movimentação lembra a forma de como as bolhas em
um reservatório de água, procuram seu próprio nível. Porém esse método, apesar de eficaz, ele
acaba, passando várias vezes pelas mesmas posições do vetor, no pior dos casos, executando o laço
novamente (voltando ao início do vetor e o percorrendo novamente), por isso não é recomendado
para programas que precisam de velocidade.
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 4/9
(http://terminaldeinformacao.files.wordpress.com/2013/05/ord_troca.gif)
Método de Troca
Trecho de código em Linguagem C, responsável pelo Bubble Sort:
void BubbleSort(int vetor[], int tamanho) 
{ 
 int aux, i, j; 
 for(j=tamanho-1; j>=1; j--) 
 { 
 for(i=0; i<j; i++) 
 { 
 if(vetor[i]>vetor[i+1]) 
 { 
 aux=vetor[i]; 
 vetor[i]=vetor[i+1]; 
 vetor[i+1]=aux; 
 } 
 } 
 } 
}
Abaixo pessoal, um exemplo de programa que criei para ser usado tanto em Linux quanto
Windows:
//Bibliotecas utilizadas
#include <stdio.h>
#include <stdlib.h>
#ifdef WIN32 //se for windows
 #define limpa_tela system("cls") //limpa tela
 #define espera sleep(500) //tempo de delay
#else //senão, ex.: linux
 #define limpa_tela system("/usr/bin/clear") //limpa tela
 #define espera sleep(1) //tempo de delay
#endif
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 5/9
main(){
 //declaração de variáveis
 int nPos=0, nAux=0;
 int nInd=0, nAtual=0;
 int nTroca=0, nChave=0;
 //Quantidade de casas do vetor
 while((nPos<=0)||(nPos>100)){
 printf("\nQuantos numeros tera o vetor? ");
 scanf("%d",&nPos);
 }
 //criando o vetor
 int nVetor[nPos], nOrig[nPos], nOpc=-1;
 //preenchendo os dados do vetor
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("\nInsira o numero %d: ",nAux+1);
 scanf("%d",&nVetor[nAux]);
 nOrig[nAux]=nVetor[nAux];
 }
 limpa_tela; //limpando a tela
 while((nOpc<=0)||(nOpc>=4)){
 printf("\n > Menu:");
 printf("\n 1. Selecao | Selection Sort");
 printf("\n 2. Insercao | Inserction Sort");
 printf("\n 3. Troca | Bubble Sort");
 printf("\n > Resposta: ");
 scanf("%d",&nOpc);
 }
 printf("\nOrdenando:\n");
 int i, j, t, m;
 if(nOpc==1){
 //Seleção
 for(nInd=0; nInd<=nPos-1; nInd++){
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("[%d]",nVetor[nAux]);
 espera;
 }
 nChave=nInd;
 for(nAtual=nInd+1; nAtual<=nPos-1; nAtual++){
 if(nVetor[nAtual]<nVetor[nChave])
 nChave=nAtual;
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 6/9
 }
 nTroca = nVetor[nChave];
 nVetor[nChave]=nVetor[nInd];
 nVetor[nInd]=nTroca;
 printf("\n");
 }
 }
 else if(nOpc==2){
 //inserção
 for ( nInd=1; nInd<nPos; nInd++){
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("[%d]",nVetor[nAux]);
 espera;
 }
 nChave = nVetor[nInd];
 nAtual = nInd-1;
 while( nAtual>=0 && nVetor[nAtual]> nChave){
 nVetor[nAtual+1] = nVetor[nAtual];
 nAtual-=1;
 nVetor[nAtual+1] = nChave;
 }
 printf("\n");
 }
 }
 else if (nOpc==3){
 //bubble - troca
 nTroca = nPos - 1 ;
 for(nInd = 0; nInd < nPos; nInd++)
 {
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("[%d]",nVetor[nAux]);
 espera;
 }
 for(nAtual = 0; nAtual < nTroca; nAtual++)
 {
 if(nVetor[nAtual] > nVetor[nAtual+1])
 {
 nAux = nVetor[nAtual];
 nVetor[nAtual] = nVetor[nAtual+1];
 nVetor[nAtual+1]=nAux;
 }
 }
 nTroca--;
 printf("\n");
 }
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 7/9
 }
 //Resultado - Vetor Original
 printf("\nOriginal: ");
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("[%d]",nOrig[nAux]);
 espera;
 }
 //Resultado - Vetor Ordenado
 printf("\nOrdenada: ");
 for(nAux=0;nAux<=nPos-1;nAux++){
 printf("[%d]",nVetor[nAux]);
 espera;
 }
 //limpando os dados e esperando o usuario apertar -Enter-
 getchar();
 printf("\n\nPressione -Enter- para finalizar!\n\n");
 getchar();
}
(http://terminaldeinformacao.files.wordpress.com/2013/05/ordenacao_no_windows.jpg)
Imagem do Programa rodando no Windows
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 8/9
(http://terminaldeinformacao.files.wordpress.com/2013/05/ordenacao_no_linux.jpg)
Imagem do Programa rodando no LinuxLembrando pessoal, que há outros métodos de ordenação, como por exemplo, o HeapShort
(desmembrado do método de Seleção, porém indexando o final, ou seja, indexando primeiramente
os maiores valores ), o QuickSort (método rápido e eficente de ordenação, onde um valor é pegado
como referência, e fazendo a ordenação através dele, exemplificado no GIF abaixo), além de outros
métodos.
(http://terminaldeinformacao.files.wordpress.com/2013/05/ord_quick.gif)
Método Quick
Referências: GIFs – Wikimedia (http://commons.wikimedia.org/)
Trechos de códigos (exemplos) – Wikipedia (http://pt.wikipedia.org/)
Bom pessoal, por hoje é só.
Abraços e até a próxima.
25/10/13 Ordenando vetores usando Linguagem C | Terminal de Informação
terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/ 9/9
#> Poderá gostar de...
$> Conceitos de Programação: Ponteiros (http://terminaldeinformacao.com/2013/03/04/conceitos-de-programacao-ponteiros/)
$> Vídeo Aula – Programando em Java #03 (http://terminaldeinformacao.com/2012/12/30/video-aula-programando-em-java-03/)
$> Conceitos de Programação: Orientação a Objeto (http://terminaldeinformacao.com/2012/12/10/conceitos-de-programacao-orientacao-a-objeto/)
(//affiliates.mozilla.org/link/banner/40977)
About these ads (http://en.wordpress.com/about-
these-ads/)