C# - Algoritmos de ordenação de dados : Inserção

 Os algoritmos de ordenação de dados podem parecer um assunto acadêmico mas na verdade estão presentes 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.

Pretendo apresentar os seguintes algoritmos em artigos :

E vou iniciar pelo algoritmo de inserção mas 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 :

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 sua implementação na linguagem C# e em VB .NET:

Abra o Visual Basic 2010 Express Edition e crie um novo projeto do tipo Windows Application com  o nome InsercaoAlgoritmo;

No formulário padrão form1.vb inclua a partir da ToolBox um controle ListBox e um botão de comando aceitando os nomes padrão;

Arranje os controles conforme o leiaute da figura abaixo:

Vamos agora definir o código irá aplicar o algoritmo de inserção para ordenar uma sequência de números em um array.

No início do formulário form1.vb vamos declarar a definição do array de 20 elementos:

'define um array de 20 elementos
Dim arr As Array = New Integer(19) {}

No evento Load do formulário vamos atribuir valores ao array e exibi-los no controle ListBox:

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load


'define os valores do array e a sua ordem

arr.SetValue(8, 0) 'primeiro

arr.SetValue(9, 1) 'segundo

arr.SetValue(2, 2) 'terceiro

arr.SetValue(4, 3)

arr.SetValue(17, 4)

arr.SetValue(5, 5)

arr.SetValue(7, 6)

arr.SetValue(3, 7)

arr.SetValue(11, 8)

arr.SetValue(27, 9)

arr.SetValue(18, 10)

arr.SetValue(1, 11)

arr.SetValue(21, 12)

arr.SetValue(40, 13)

arr.SetValue(10, 14)

arr.SetValue(15, 15)

arr.SetValue(6, 16)

arr.SetValue(13, 17)

arr.SetValue(19, 18)

arr.SetValue(14, 19)

 

Me.Text = "Algoritmo de ordenação por inserção"

'exibe os valores do array no listbox

For i As Integer = 0 To arr.Length - 1

   lista.Items.Insert(i, arr.GetValue(i))

Next
 

End Sub

No evento Click do botão Ordenar vamos incluir o código que faz a chamada a rotina de inserção e exibe os elementos ordenados:

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click


'chama a rotina de ordenação

ordenacaoPorInsercao()

'limpa o listbox

lista.Items.Clear()


'exibe os valores ordenados

For x As Integer = 0 To arr.Length - 1

    lista.Items.Insert(x, arr.GetValue(x))

Next
 

End Sub

 

Agora vejamos o código principal que faz a ordenação usando o algoritmo de inserção:

Private Sub ordenacaoPorInsercao()


'define a variável temp

Dim temp As Integer = 0


'define as variáveis i e k

Dim j As Integer = 0

Dim k As Integer = 0


'percorre o array

For j = 1 To (arr.Length) - 1

    'obtem um valor do array e guarda em temp

    temp = CInt(arr.GetValue(j))


     'atribui a k o valor de j-1

     k = j - 1

     'Executa enquando k for maior e igual a zero e tambem o valor do índice k do array for maior que  temp

    'temp é o valor obtido do segundo elemento então ele esta comparando o anterior com o próximo

     While k >= 0 AndAlso CInt(arr.GetValue(k)) > temp

         'efetua a inserção do valor

         arr.SetValue(arr.GetValue(k), k + 1)

          k = k - 1

     End While

     'atribui o valor no array

     arr.SetValue(temp, k + 1)

Next
 

End Sub

Uma versão para esta rotina na Linguagem C# pode ser vista no código a seguir:

static int[] ordenar(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;

}

Executando o projeto Visual Basic iremos obter o resultado conforme mostrado abaixo:

Existe muita informação com artigos e vídeos na web sobre este importante assunto que são os algoritmos de ordenação.

Simples , simples assim...

Pegue o projeto VB .NET completo aqui: InsercaoAlgoritmo.zip

Pegue o projeto C# completo aqui: AlgoritmoInsercao.zip

Aguarde o próximo artigo sobre algoritmos de ordenação.

Eu sei é apenas Visual Basic e C# , mas eu gosto.

Referências:

José Carlos Macoratti