쉘 정렬(Shell sort)

u      삽입 정렬을 간단하게 변형
u      멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴
u      h-정렬 화일 : 모든 h번째 원소를 정렬한 화일
u      증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1
u      특징
Ø       순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교회수는 N 3/2 을 넘지 않음
Ø       안정적인 제자리 정렬

ShellSort(a[], n)
  for (h ← 1; h <n; h ← 3*h+1) do { }; // 첫 번째 h 값 계산
  for ( ; h >0; h ← h/3) do { // h 값을 감소시키며 진행
    for (i ← h + 1; i ≤ n; i ← i+1) do {
       v ← a[i];
       j ← i;
      while (j >h and a[j-h] >v) do {
             a[j] ← a[j-h];
             j ← j-h;
       } // while
       A[j] ← v;  
     } // for
   } // for
end ShellSort()


void Shellsort()
{
    int i, j, h, v;                  
        for(h=1 ; h<=ARRSIZE ; h=3*h+1);  
                                     
        for( ; h>0 ; h/=3)    
    {
               for(i=h+1 ; i<=ARRSIZE ;i++)
        {
                       v=buf[i]; j=i;
                       while(j>h&&buf[j-h]>v)
                       {
                buf[j] = buf[j-h];
                j -= h;
            }
                       buf[j] = v;
               }
    }
}


u      1960년 C.A.R. Hoare에 의해 개발
u      분할 정복(divide and conquer) 기법을 사용한 정렬 방법의 하나
u      현재 가장 광범위하게 쓰이는 정렬 알고리즘
u      퀵 정렬의 성능을 개선하려는 시도가 있었지만 큰 성과를 거두지 못함
u      특징
Ø       평균적으로 아주 좋은 성능을 가짐
Ø       약간의 작은 스택만 있으면 별도의 메모리를 요구하지 않음
Ø       불안정적인 제자리 알고리즘
Ø       N 개의 원소를 정렬하는데 평균적으로 N logN 의 연산속도를 가짐