Shell Sort Algorithm.

1. 삽입정렬의 단점을 개선한 알고리즘 (Shell Sort)

1.1. 삽입정렬의 단점
: 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보이나, 그렇지 않은 경우에는 매우 느린 속도를 보인다. 이는 바로 인접한 요소와 비교를 하기 때문이다. 그래서 만약 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동이 필요.

1.2. 개선책
: 'h'만큼의 간격'으로 떨어진 레코드를 삽입 정렬하는 방법.

void shell_sort(int a[], int n)
{
int i, j, k, h, v;

for (h = n / 2; h > 0; h /= 2;) // h <- h/2
{
for (i = 0; i < h; i++) //변이
{
for (j = i + h; j < n; j += h)
{
v = a[j];
k = j;

while(k > h-1 && a[k-h] > v)
{
a[k] = a[k-1]; //이동
k -= h;
}
a[k] = v; //삽입
}
}
}
}

2. 예를 들어 h가 10이라면 0,10,20,30,40...의 요소간의 삽입정렬을 하고 1씩 더한 1,11,21,31,41...의 요소간의 삽입정렬을 하는 식으로 h까지 i를 1씩 증가시키면서 h에 더하여 정렬하기를 반복한다.
정렬이 끝나면 h를 반으로 나누어 또다시 위의 과정을 반복하고,
h가 1이 되면 이미 배열은 거의 다 정렬되어 있는 상태여서 매우 빠른 속도로 삽입 정렬이 가능하다.

3. 입력 자료의 형태에 별로 상관없이 뛰어난 속도를 보인다. 최악의 자료배열인 역순 배열일 경우에도 그다지 큰 차이를 보이지 않는다.
실제로 가장 빠르다는 퀵소트의 경우 20,000개 정도의 정수를 정렬하기에는 힘이 든다.(내부 스택을 사용하는 재귀호출을 사용하므로, 메모리가 부족하기 때문) 하지만, 쉘 정렬은 추가로 메모리가 필요하지 않다는 장점.

4. 하지만, 또다시 개선하여 더욱 우수한 알고리즘을 만들 수 있다.
쉘정렬의 성능은 'h의 설정'에 따라 달라지는데, Robert Sedgewick의 연구결과 최선의 h 수열이 밝혀졌다.
h(n) = 3 * h(n-1) + 1, h(1) = 1 //괄호안의 n은 배열의 길이
즉, 1, 4, 13, 40, 121, 364, 1093

＊ 위 함수의 h를 설정하는 부분의 for문을 다음으로 대체하면, 그 성능은 눈에띄게 좋아진다.
for (h = 1; h < n; h = 3 * h + 1)