algorithm
Shell Sort

Shell ordina le informazioni di base

L'ordinamento di shell , noto anche come ordinamento a incremento decrescente, è uno dei più vecchi algoritmi di ordinamento, dal nome del suo inventore Donald. L. Shell (1959). È veloce, facile da capire e facile da implementare. Tuttavia, la sua analisi della complessità è un po 'più sofisticata.

L'idea di ordinare Shell è la seguente:

1. Disporre la sequenza di dati in una matrice bidimensionale
2. Ordina le colonne dell'array

L'ordinamento di shell migliora l'ordinamento di inserimento. Inizia confrontando elementi distanti tra loro, quindi elementi meno distanti e infine confrontando elementi adiacenti (in pratica un tipo di inserzione).

L'effetto è che la sequenza di dati è parzialmente ordinata. Il processo sopra è ripetuto, ma ogni volta con una matrice più stretta, cioè con un numero minore di colonne. Nell'ultimo passaggio, l'array è costituito da una sola colonna.

Esempio di ordinamento Shell:

Pseudo codice per 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
    }
}

Spazio ausiliario: O(n) total, O(1) auxiliary
Complessità del tempo: O(nlogn)

Implementazione 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;
    }
}