algorithm
셸 정렬

셸 기본 정보 정렬

감소 정렬 (increment increment sort )이라고도 알려진 쉘 정렬 은 발명가 인 Donald의 이름을 따서 명명 된 가장 오래된 정렬 알고리즘 중 하나입니다 . L. Shell (1959). 이해하기 쉽고 구현하기 쉽습니다. 그러나 복잡성 분석은 좀 더 정교합니다.

쉘 정렬의 아이디어는 다음과 같습니다.

1. 데이터 시퀀스를 2 차원 배열로 정렬
2. 배열 열 정렬

쉘 정렬은 삽입 정렬을 개선합니다. 먼저 멀리 떨어진 요소를 비교 한 다음 멀리 떨어져있는 요소를 비교하고 마지막으로 인접한 요소를 비교하여 시작합니다 (효과적으로 삽입 정렬).

결과적으로 데이터 시퀀스가 ​​부분적으로 정렬됩니다. 위의 프로세스가 반복되지만 매번 더 좁은 배열, 즉 더 적은 수의 열로 반복됩니다. 마지막 단계에서 배열은 단 하나의 열로 구성됩니다.

셸 정렬의 예 :

셸 정렬에 대한 의사 코드 :

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

보조 공간 : O(n) total, O(1) auxiliary
시간 복잡성 : O(nlogn)

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