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:

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.

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.

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
 
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;
      }
      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");
    }
  }
 
  //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();
}

Imagem do Programa rodando no Windows

Imagem do Programa rodando no Linux

Lembrando 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.

Método Quick

Referências: GIFs – Wikimedia
Trechos de códigos (exemplos) – Wikipedia

Update 15/06/2015:
Caso você queria, foi feita uma postagem com exemplos de Shell Sort e Quick Sort, leia aqui.

Bom pessoal, por hoje é só.
Abraços e até a próxima.

Tags: Linguagem C