Métodos Simples de Ordenação

Pra que?

Tornar mais simples e rápido recuperar determinada informação dentro de um conjunto enorme de informações.

Quais são os tipos simples?

• Troca
• Seleção
• Inserção

Aviso

Não existe um método de ordenação que seja universalmente reconhecido como o melhor, que atende a todas as necessidades e seja o único que você precisa saber. Não. Se alguém te disser isso, ignore. Cada caso é um caso e é necessário analisá-lo antes de decidir qual melhor método se aplica a sua necessidade.

Ordenação por Troca

Bubble Sort - Bolha

Neste tipo de ordenação dois elementos são comprados e se o segundo for menor que o primeiro ocorrerá a troca desses elementos numa passagem direta por uma lista (não volta atrás).

Vantagem: estabilidade e simplicidade do algoritmo
Desvantagem: lentidão.

Procedimento (em C) para ordenar o vetor V de números inteiros em que tam é o tamanho do vetor V.

void bubbleSort (int v[], int tam)
{
  int i, j, aux;
  for(j=0; j<tam-1;j++)
    for (i=0;i<tam-1;i++)
    {
      if(a[i]>a[i+1])
      {
      aux = a[i];
      a[i] = a[i+1];
      a[i+1] = aux;
      }
    }
}

Ordenação por Inserção

Insertion Sort

Neste método é feita uma única passagem com vários retornos.
Dois elementos são comparados iniciando no segundo numero da sequência de números que desejamos ordenar. Se o primeiro for maior que o segundo, há a troca entre esses números. Depois, pegamos o terceiro número da sequência e comparamos com o segundo elemento, se o segundo for maior que o terceiro, eles trocam de lugar; a comparação continua entre o segundo e o primeiro; sendo o segundo maior que o primeiro haverá troca de posições caso contrário, nada é feito. O próximo número é o quarto.... e vamos "voltando" e comparando até terminar a sequência.

Vantagem: simplicidade do algoritmo (mais rápido que o BubbleSort)
Desvantagem: lento

void InsertionSort(int v[], int tam)
{
int i,j,aux;
  for(i=1;i<tam;i++)
  {
    aux = v[i];
    j=i-1;
    while (j>=o && v[j]>aux)
    {
      v[j+1] = v[j];
      j=j-1;
    }
    v[j+1] = aux;
  }
}

Ordenação por Seleção

Selection Sort

A cada passagem o menor elemento do vetor é selecionado e colocado na sua posição correta. Durante a ordenação a parte do vetor já ordenada é desconsiderada.
Pegamos o primeiro elemento do vetor e armazenamos seu índice. O vetor inteiro é percorrido a procura de um numero menor que o primeiro. Caso esse número exista, o índice dele é armazenado e a troca é feita, assim por diante..  Neste método de ordenação é o "contrário" do Insertion Sort. Ao invés de voltarmos o vetor, o percorremos a partir do primeiro.

Vantagem: simplicidade do algoritmo
Desvantagem: lentidão.

void SelectionSort (int v[], int tam)
{
int i,j,aux, indiceAux;
  for(i=0;i<(tam-1);i++)
  {
    aux = v[i];
    indiceAux = i;
    for(j=(i+1);i<tam;i++)
    {
      if(v[j] < aux)
      {
        aux = v[j];
        indiceAux = j;
      } 
      v[indiceAux] = v[i];
      v[i] = aux;
    }
  }
}