6-5. 셸 정렬(Shell Sort)

단순 삽입 정렬의 특징

 

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

셸 정렬은 이러한 단순 삽입 정렬의 장점을 살리고 단점은 보완한 알고리즘이다.

 

 

 

 

 

셸 정렬

: 단순 삽입 정렬의 장점(a)은 살리고 단점(b)은 보완한 정렬 알고리즘으로, 도널드 셸(D. L. Shell)이 고안

 

• 먼저, 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행
• 각 그룹을 합치면서 정렬을 반복해 요소의 이동 횟수를 줄임

 

 

 

[예시]

먼저, 배열을 ※4개의 그룹으로 나누고 각 그룹별로 정렬 (4-정렬)

 

※4칸씩 떨어져있는 요소들로 묶음({8, 7}, {1, 6}, {4, 3}, {2, 5})

 

 

 

4-정렬을 마친 상태에서 2개의 그룹({7, 3, 8, 4}, {1, 2, 6, 5})으로 나누어 2-정렬

 

 

 

마지막으로 1-정렬을 적용해 정렬을 마무리

 

 

 

총 7회의 정렬로 정렬을 마침

 

 

 

[정리]

1. 2개 요소에 대해 '4-정렬'을 수행(4개의 그룹)
2. 4개 요소에 대해 '2-정렬'을 수행(2개의 그룹)
3. 8개 요소에 대해 '1-정렬'을 수행(1개의 그룹)

 

: 단순 삽입 정렬에 비해 정렬해야 하는 횟수는 늘지만, 전체적으로는 요소의 이동 횟수가 줄어 효율적으로 정렬할 수 있음

 

 

 

[실습 코드]

static void shellSort(int[] a, int n) {
        for(int h = n / 2; h > 0; h /= 2) {
            for(int i = h; i < n; i++) {
                int j;
                int tmp = a[i];
                for(j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                    a[j + h] = a[j];
                }
                a[j + h] = tmp;
            }

 

 

 

 

 

증분값(h값)의 선택

 

위의 소스코드에서는 h값을 아래와 같이 변화

h = 4, 2, 1

 

→ 이러한 방식은 배열의 요소들이 충분히 섞이지 않음

 

 

 

• 개선

요소들이 충분히 섞이지 않는 문제를 해결하기 위해서는 h값이 서로 배수가 되지 않도록 함

h = ..., 121, 40, 13, 4, 1

 

• 1부터 시작해 3배한 값에 1을 더하는 수열을 거꾸로 나열
• h의 초깃값은 너무 크면 효과가 없기 때문에 배열의 요솟수 n을 9로 나눈 값을 넘지 않도록 함

 

 

 

[실습 코드]

static void shellSort(int[] a, int n) {
        int h;
        for(h = 1; h < n / 9; h = h * 3 + 1);
        
        for( ; h > 0; h /= 3) {
            for(int i = h; i < n; i++) {
                int j;
                int tmp = a[i];
                for(j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                    a[j + h] = a[j];
                }
                a[j + h] = tmp;
            }

 

 

 

기존의 알고리즘보다 시간 복잡도는 향상되었으나, 멀리 떨어져 있는 요소를 교환한다는 점에서 이 알고리즘도 안정적이지 않다.