[알고리즘] 셸 정렬 (Shell Sort)

단순 삽입 정렬의 장점(a)은 살리고 단점(b)은 보완한 정렬 알고리즘. 퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었다.

a: 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.
b: 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다.

 

정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 

 

코드

 // 셸 정렬 함수
 void shell(int a[], int n) {
     int i, j, h;
     
     for(h = n/2; h > 0; h/=2) {
         for(i = h; i < n; i++) {
             int tmp = a[i];
             for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
                 a[j + h] = a[j];
             }
             a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
         }
     }
 }

 

단순 삽입 정렬과 다르게 그룹을 나누면서 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.

셸 정렬의 시간복잡도 : 간격에 따라 O(n^1.25) ~ O(n^1.5)

 

 

셸 정렬 알고리즘 개선 - 1

증분값 h가 서로 배수가 되지 않도록 조정하면 요소가 충분히 섞여 효율적인 정렬을 기대할 수 있다.
-> 1부터 시작하여 3배한 값에 1을 더하는 수열을 이용하고, h의 초깃값은 너무 크면 효과가 없기 때문에 배열의 요소 개수 n을 9로 나눈 값을 넘지 않도록 정한다.

코드

 // 셸 정렬 함수(버전 2 : h = ..., 121, 40, 13, 4, 1)
 void shell(int a[], int n) {
     int i, j, h;
     
     for(h = 1; h < n / 9; h = h * 3 + 1)
     ;
     
     for(; h > 0; h/=3) {
         for(i = h; i < n; i++) {
             int tmp = a[i];
             for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
                 a[j + h] = a[j];
             }
             a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
         }
     }
 }