algorithm
Sortuj powłoki

Podstawowe informacje o sortowaniu powłoki

Sortowanie skorupowe , znane również jako malejące sortowanie przyrostowe, jest jednym z najstarszych algorytmów sortowania, nazwanym tak od nazwiska jego wynalazcy Donalda. L. Shell (1959). Jest szybki, łatwy do zrozumienia i łatwy do wdrożenia. Jednak jego analiza złożoności jest nieco bardziej złożona.

Pomysł sortowania powłoki jest następujący:

1. Ułóż sekwencję danych w tablicy dwuwymiarowej
2. Posortuj kolumny tablicy

Sortowanie skorupy poprawia sortowanie wstawiania. Zaczyna się od porównania elementów daleko od siebie, następnie elementów mniej oddalonych od siebie, a na koniec porównania sąsiednich elementów (w efekcie rodzaju wstawiania).

W rezultacie sekwencja danych jest częściowo posortowana. Powyższy proces powtarza się, ale za każdym razem z węższą tablicą, tj. Z mniejszą liczbą kolumn. W ostatnim kroku tablica składa się tylko z jednej kolumny.

Przykład sortowania powłoki:

Pseudo kod dla 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
    }
}

Przestrzeń pomocnicza: O(n) total, O(1) auxiliary
Złożoność czasu: O(nlogn)

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