algorithm
Shell Sort

Shell-Basisinformationen

Die Shell-Sortierung , auch als abnehmende Inkrement-Sortierung bezeichnet, ist einer der ältesten Sortieralgorithmen, benannt nach ihrem Erfinder Donald. L. Shell (1959). Es ist schnell, leicht verständlich und einfach zu implementieren. Die Komplexitätsanalyse ist jedoch etwas komplexer.

Die Idee der Shell-Sortierung ist folgende:

1. Ordnen Sie die Datensequenz in einem zweidimensionalen Array an
2. Sortieren Sie die Spalten des Arrays

Die Shell-Sortierung verbessert die Sortierreihenfolge. Es beginnt damit, Elemente weit auseinander zu vergleichen, dann weniger weit auseinander und schließlich benachbarte Elemente zu vergleichen (effektiv eine Einfügesortierung).

Der Effekt ist, dass die Datensequenz teilweise sortiert ist. Der obige Vorgang wird wiederholt, jedoch jeweils mit einem engeren Array, dh mit einer kleineren Anzahl von Spalten. Im letzten Schritt besteht das Array nur aus einer Spalte.

Beispiel für eine Shell-Sortierung:

Pseudocode für 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
    }
}

Hilfsraum: O(n) total, O(1) auxiliary
Zeitkomplexität: O(nlogn)

C # -Implementierung

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