algorithm
Shell Sort

Shell Sort Basic-informatie

Shell-sort , ook bekend als de afnemende increment-sortering, is een van de oudste sorteeralgoritmen, genoemd naar zijn uitvinder Donald. L. Shell (1959). Het is snel, gemakkelijk te begrijpen en gemakkelijk te implementeren. De complexiteitsanalyse is echter iets geavanceerder.

Het idee van Shell-sortering is het volgende:

1. Rangschik de gegevensreeks in een tweedimensionale array
2. Sorteer de kolommen van de array

Shell sort verbetert de invoegsortering. Het begint met het vergelijken van elementen ver uit elkaar, dan elementen minder ver uit elkaar, en ten slotte het vergelijken van aangrenzende elementen (in feite een invoegtype).

Het effect is dat de gegevensreeks gedeeltelijk is gesorteerd. Het bovenstaande proces wordt herhaald, maar elke keer met een kleinere array, dat wil zeggen met een kleiner aantal kolommen. In de laatste stap bestaat de array uit slechts één kolom.

Voorbeeld van Shell-soort:

Pseudo-code voor 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
    }
}

Hulpruimte: O(n) total, O(1) auxiliary
Tijd Complexiteit: O(nlogn)

C # Implementatie

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