C# - Algoritmos de ordenação

C# - Algoritmos de ordenação - III

Hoje vamos continuar apresentando os algoritmos de ordenação usando a linguagem C#.

Continuando o artigo anterior vamos tratar agora do algoritmo de ordenação Insertion Sort.

Ordenação com Insertion Sort

O algoritmo de ordenação Insertion Sort percorre um array ordenando os elementos à esquerda a medida que avança percorrendo o array.

O array ordenado é construído na parte inferior do array a partir de onde é inserido repetidamente o próximo elemento na parte ordenada do array deslizando-o para sua posição adequada.

O número de trocas é tanto quanto o usado no Bubble Sort pois apenas uma inversão é removida por troca e portanto esta ordenação também requer O(N2) trocas.

Em média, a ordenação por inserção requer apenas metade das comparações feitas via Bubble Sort, uma vez que a distância média que um elemento deve se mover para entrada aleatória é a metade do comprimento da parte classificada.

Este método de ordenação é útil para pequenas entradas e possui muitas trocas e menos comparações sendo de fácil implementação.

A seguir temos uma implementação da ordenação com Insertion Sort no C#:

using System;

namespace Insertion_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numeros = { 230, 45, 345, 4, 324, 90, 76, 34, 67, 11 };
            Console.WriteLine("######## Ordenação com Insertion Sort ########\n");
            Console.WriteLine("Array original\n");
            foreach (int numero in numeros)
                Console.Write($"{numero} ");

            Console.WriteLine("\n\nOrdenando o array usando Insertion Short\n");

            int[] arrayOrdenado = IntArrayInsertionSort(numeros);

            Console.WriteLine("Array Ordenado\n");

            foreach (int numero in arrayOrdenado)
                Console.Write($"{numero} ");

            Console.ReadLine();
        }

        public static int[] IntArrayInsertionSort(int[] data)
        {
            int i, j;
            int N = data.Length;

            for (j = 1; j < N; j++)
            {
                for (i = j; i > 0 && data[i] < data[i - 1]; i--)
                {
                    TrocarValores(data, i, i - 1);
                }
            }
            return data;
        }

        public static int[] TrocarValores(int[] arrayDados, int m, int n)
        {
            int temp;
            temp = arrayDados[m];
            arrayDados[m] = arrayDados[n];
            arrayDados[n] = temp;
            return arrayDados;
        }
    }
}

Uma implementação alternativa sem usar métodos auxiliares pode ser vista a seguir:

public static int[] InsertionSort(int[] array)
{
        int i, j, atual;
        for (i = 1; i< array.Length; i++)
        {
            atual = array[i];
            j = i;
            while ((j > 0) && (array[j - 1] > atual))
            {
                array[j] = array[j - 1];
                   j = j - 1;
            }
            array[j] = atual;
         }
         return array;
}

Executando o projeto teremos o resultado abaixo :

Pegue o projeto completo aqui: Algoritmos_Ordenacao_3.zip

Na próxima parte do artigo veremos o algoritmo de ordenação shell sort.

"Quem, pois, tiver bens do mundo, e, vendo o seu irmão necessitado, lhe cerrar as suas entranhas, como estará nele o amor de Deus? Meus filhinhos, não amemos de palavra, nem de língua, mas por obra e em verdade."
1 João 3:17,18

Referências:

José Carlos Macoratti