C# - Algoritmos de ordenação de dados

Os algoritmos de ordenação de dados podem parecer um assunto acadêmico mas na verdade esta presente a todo momento em nossas vidas e nos sistemas que desenvolvemos. Muitas vezes as linguagens atuais trazem recursos que permitem que com um único comando seja feita a ordenação de uma estrutura de dados e muitas vezes não nos percebemos da importância que esta por trás disso.

Meu objetivo neste artigo é apresentar os principais algoritmos de ordenação para que possamos estudá-los e compreendê-los melhor.

Temos os seguintes algoritmos de ordenação :

  1. Inserção
  2. BubbleSort
  3. QuickSort
  4. MergeSort
  5. ShellSort

E neste artigo vou apresentar o primeiro deles.

Antes de iniciar a parte prática vamos a um pouco de teoria...

O algoritmo de ordenação por inserção

Comecei por este por ser o mais simples e intuitivo; ele é baseado em ações que praticamos no dia dia para realizar ordenações simples com um pequeno número de elementos.

O algoritmo de ordenação por inserção é muito eficiente quando aplicado a um pequeno número de elementos e funciona assim:

- Percorre-se um vetor de elementos da esquerda para a direita e à  medida que se avança se vai deixando os elementos mais à esquerda ordenados.(Inseridos no final do vetor);

Este método é exatamente o que usamos quando temos algumas cartas de baralho para ordenar.

Uma implementação simples deste algoritmo necessita de duas estruturas de listas : a lista fonte e a lista na qual os itens são inseridos ordenados.

Este algoritmo é mais eficiente que o Bubble Sort e que o algoritmo Selection Sort e pode ser usado com eficácia para ordenações de até 1000 itens.

Vejamos a seguir o código que podemos usar na linguagem C# e em VB .NET para aplicar esse algoritmo:

static int[] ordernar(int[] A)

{

   int i, j, index;

   for (i = 1; i < A.Length; i++)

   {

      index = A[i];

       j = i;

       while ((j > 0) && (A[j - 1] > index))

      {

          A[j] = A[j - 1];

          j = j - 1;

      }

      A[j] = index;

   }

    return A;

}

  Private Sub Ordenacao(Numeros() As Integer)
       Dim i As Long
       Dim j As Long
       Dim iMin As Long
       Dim iMax As Long
       Dim varSwap As Variant
       iMin = LBound(Numeros) + 1
       iMax = UBound(Numeros)
       For i = iMin To iMax
           varSwap = Numeros(i)
           For j = i To iMin Step -1
               If varSwap < Numeros(j - 1) Then Numeros(j) = Numeros(j - 1) Else Exit For
           Next j
          Numeros(j) = varSwap
       Next i
End Sub
 

Algoritmo de ordenação por inserção

Esse algoritmo, como muitos outros, é baseado em ações que nós (como pessoas) fazemos no dia-a-dia para resolver o problema. Lembra quando você está jogando baralho, e suas cartas já estão na mesa e você precisa colocá-las na mão de uma forma ordenada?

Essa ordenação deve ser feita de uma maneira que você esteja acostumado a escolher uma carta facilmente para jogar mais rápido e melhor...

É exatamente isso que o algoritmo de ordenação por inserção faz por baixo dos panos.

A idéia principal dele é: adiciona-se um item qualquer à estrutura de dados, depois, para cada item que ainda não esteja na estrutura, antes de adicioná-la, comparar com cada item que já está nela (consequentemente já ordenada) até encontrar a posição a ser encaixada.

É exatamente o que fazemos com o baralho.

Essa opção é boa quando temos uma entrada pequena de dados, para entradas grandes pode se consumir muito tempo de processamento.

Na próxima parte do artigo vamos continuar mostrando a implementação ...


Referências:

José Carlos Macoratti