C# - Algoritmos de ordenação

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

O Shell Sort é basicamente um truque para fazer a ordenação Insertion Sort ser executada mais rapidamente. Se você der uma olhada rápida no código e vai perceber que além da presença de dois laços externos adicionais o código é muito semelhante.

Como o Insertion Sort remove uma inversão por troca, ele não pode ser executado mais rápido do que o número de inversões nos dados, que no pior caso é O (N2)

O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. (wikipédia)

O truque no Shell Sort é começar trocando elementos que estão mais separados. Embora isso possa remover apenas uma inversão às vezes, muitas vezes muitas mais inversões são removidas com elementos intermediários. A ordenação Shell considera as subseqüências de elementos espaçados por k elementos. Existem k dessas seqüências começando nas posições 0 a k-1 no array. Nesses tipos, os elementos separados por k posições são trocados, removendo entre 1 e 2 (k-1) inversões +1.

Trocar elementos distantes não é suficiente, geralmente, então um Shell Sort fará várias passagens com valores decrescentes de k, terminando com k = 1.

using System;

namespace Shell_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 Shell Sort ########\n");
            Console.WriteLine("Intervalos [1, 2, 4, 8]\n");

            Console.WriteLine("Array original\n");
            foreach (int numero in numeros)
                Console.Write($"{numero} ");

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

            int[] intervalos = { 1, 2, 4, 8 };
            int[] arrayOrdenado = IntArrayShellSort(numeros, intervalos);

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

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

            Console.ReadLine();
        }
        public static int[] IntArrayShellSort(int[] data, int[] intervalos)
        {
            int i, j, k, m;
            int N = data.Length;

            // Os intervalos precisam ter uma ordenação ascendente
            for (k = intervalos.Length - 1; k >= 0; k--)
            {
                int intervalo = intervalos[k];
                for (m = 0; m < intervalo; m++)
                {
                    for (j = m + intervalo; j < N; j += intervalo)
                    {
                        for (i = j; i >= intervalo && data[i] < data[i - intervalo]; i -= intervalo)
                        {
                            TrocarValores(data, i, i - intervalo);
                        }
                    }
                }
            }
            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;
        }
    }
}

No exemplo classificamos todas as subsequências dos elementos 8 à parte, depois 4, 2 e 1. Observe que esses intervalos são para mostrar como o método funciona - não como o método funciona melhor.

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

        public static int[] ShellSort(int[] array)
        {
            int h = 1;
            int n = array.Length;

            while (h < n)
            {
                h = h * 3 + 1;
            }

            h = h / 3;
            int c, j;

            while (h > 0)
            {
                for (int i = h; i < n; i++)
                {
                    c = array[i];
                    j = i;
                    while (j >= h && array[j - h] > c)
                    {
                        array[j] = array[j - h];
                        j = j - h;
                    }
                    array[j] = c;
                }
                h = h / 2;
            }
            return array;
        }

Aquele que crê no Filho (Jesus) tem a vida eterna; mas aquele que não crê no Filho não verá a vida, mas a ira de Deus sobre ele permanece.
João 3:36