쉘 정렬 Shell Sort

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 쉘 정렬 개념

입력 파일에 있는 레코드들을 여러 개의 서브파일로 다시 구성하고 각 서브파일을 삽입 정렬 방법에 의해 순서적으로 배열하는 과정을 반복한 것
주어진 리스트를 적당한 매개 변수의 값만큼 서로 떨어진 레코드들과 비교하여 교환하는 과정을 매개 변수 값을 바꾸어가며 반복

■ 쉘 정렬 특징

삽입정렬의 개념을 확대하여 일반화한 정렬 방법
알고리즘이 간단하여 프로그램으로 쉽게 구현
수행 능력도 삽입 정렬보다 우수한 것으로 평가
멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이타가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블 정렬 방식의 단점을 해결

■ 쉘 정렬 방법

쉘 정렬에서 서브파일을 결정하는 매개 변수의 값 h에 따라 h만큼 떨어져 있는 레코드들은 하나의 서브파일로 구성
입력 파일을 구성하는 레코드들은 h만큼 떨어져 위치한 레코드들과 비교하여 레코드의 키 값에 따라 교환하는 과정을 매개 변수를 감소시켜 1이 될 때까지 반복
매개변수의 값 h를 증분이라고 하며, h는 서브파일의 수와 같음


■ 예를 들어, 증분 h가 4이면 서브파일은,    

X[1], X[5], X[9], …

X[2], X[6], X[10], …

X[3], X[7], X[11], …

X[4], X[8], X[12], …

로 구성되어 부분 정렬이 이루어지며, 증분 h를 감소시켜 새로운 서브파일을 구성하여 정렬시킨다.

증분 h가 1이 될 때까지 위의 과정을 반복 수행하면 최종적으로 정렬된 하나의 전체 파일이 구성



■ n=8일 때, 정렬 간격(매개변수) 4, 2, 1로 입력 레코드 8, 3, 5, 6, 2, 1, 7, 4에 대한 쉘 정렬 과정



▷ 수행 1회 : 매개변수 4

증분=4
8 3 5 6 2 1 7 4

정렬 후
2 1 5 4 8 3 7 6


▷ 수행 2회 : 매개변수 2

증분=2
2 1 5 4 8 3 7 6

정렬 후
2 1 5 3 7 4 8 6



▷ 수행 3회 : 매개변수 1

증분=1
2 1 5 3 7 4 8 6

정렬 후
1 2 3 4 5 6 7 8


■ 쉘 정렬 알고리즘

------------------------------------------------------
void Shellsort(int A[], int N)
{
    int i, j, Increment;
    int Tmp;
    for(Increment=N/2; Increment>0; Increment/=2)
        for(i=Increment; i<N; i++)
        {
            Tmp=A[i];
            for(j=i; j>=Increment; j-=Increment)
                if(Tmp < A[j-Increment])
                    A[j]=A[j-Increment];
                else
                    break;
                A[j]=Tmp;
        }
}
------------------------------------------------------



■ 성능



▷ 발생하는 비교 횟수는 정렬 간격(매개변수의 값)이 수행속도 좌우
▷ 매개 변수는 근사적으로 소수이어야 한다고 알려져 있으며,
     이러한 경우의 알고리즘 수행시간은 O(N(logN)2)

▷ Shell(N/2) 최악의 경우 O(N2)
▷ Hibberd 간격 1, 3, 7, 15, ..., (2k-1) 최악의 경우 O(N3/2)

▷ Sedgewick 간격 9·4i-9·2i+1 또는 4i-3*2i+1
      { 1, 5, 9, 19, 41, 109, ... } worst O(N4/3), average O(N7/6)

▷ 쉘 정렬을 구현할 때에는 정렬간격을 배열에 저장하여 사용함
▷ 인접요소의 교환방법 개선책임, 최악 N2, 실제로 N1.5,  N1.3
▷ 쉘 정렬은 퀵 정렬 다음으로 수행속도가 빠르고 안정적