algorithm
Shell Sort

Shell Sort Basic Information

Shellsortering , även känd som den minskande ökningen, är en av de äldsta sorteringsalgoritmerna, uppkallad efter sin uppfinnare Donald. L. Shell (1959). Det är snabbt, enkelt att förstå och enkelt att implementera. Men dess komplexitetsanalys är lite mer sofistikerad.

Idén med Shell-sortering är följande:

1. Ordna datasekvensen i en tvådimensionell matris
2. Sortera kolumnerna i matrisen

Skal sortering förbättrar insättningssorteringen. Det börjar med att jämföra element långt ifrån varandra, sedan element som är mindre långt ifrån varandra och slutligen jämföra intilliggande element (effektivt en insättningssortering).

Effekten är att datasekvensen delvis sorteras. Processen ovan upprepas, men varje gång med en smalare grupp, dvs med ett mindre antal kolumner. I det sista steget består matrisen av endast en kolumn.

Exempel på Shell-sort:

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

Hjälputrymme: O(n) total, O(1) auxiliary
Tidskomplexitet: O(nlogn)

C # Implementering

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