algorithm
Shell Sort

Información básica de Shell Sort

La clasificación de shell , también conocida como la clasificación de incremento decreciente, es uno de los algoritmos de clasificación más antiguos, que lleva el nombre de su inventor Donald. L. Shell (1959). Es rápido, fácil de entender y fácil de implementar. Sin embargo, su análisis de complejidad es un poco más sofisticado.

La idea de la ordenación de Shell es la siguiente:

1. Organizar la secuencia de datos en una matriz bidimensional.
2. Ordenar las columnas de la matriz.

La ordenación de la carcasa mejora la ordenación por inserción. Comienza comparando elementos muy separados, luego elementos menos separados, y finalmente comparando elementos adyacentes (de hecho, una clasificación por inserción).

El efecto es que la secuencia de datos está parcialmente ordenada. El proceso anterior se repite, pero cada vez con una matriz más estrecha, es decir, con un número menor de columnas. En el último paso, la matriz consta de una sola columna.

Ejemplo de ordenación de Shell:

Pseudo código para Shell Sort:

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

Espacio auxiliar: O(n) total, O(1) auxiliary
Complejidad del tiempo: O(nlogn)

Implementación de C #

public class ShellSort
{
    static void SortShell(int[] input, int n)
    {
        var inc = 3;
        while (inc > 0)
        {
            int i;
            for (i = 0; i < n; i++)
            {
                var j = i;
                var temp = input[i];
                while ((j >= inc) && (input[j - inc] > temp))
                {
                    input[j] = input[j - inc];
                    j = j - inc;
                }
                input[j] = temp;
            }
            if (inc / 2 != 0)
                inc = inc / 2;
            else if (inc == 1)
                inc = 0;
            else
                inc = 1;
        }
    }

    public static int[] Main(int[] input)
    {
        SortShell(input, input.Length);
        return input;
    }
}