[C언어 알고리즘] 정렬(5) - 쉘정렬(Shell sort)

삽입정렬(Insertion sort)은 이미 정렬되어 있는 경우나 대충 정렬되어 있는 경우 좋은 성능을 보이지만 그렇지 않은 경우 속도가 매우 느립니다. 왜냐면 삽입정렬은 인접한 요소와 비교를 하기 때문인데 역순으로 배열된 경우 가장 작은 값이 맨 뒤에 있으므로 배열의 크기만큼 비교와 이동을 해야해서 비효율적입니다.

쉘정렬(Shell sort)는 이런 문제점을 개선하기 위해 일정 간격으로 떨어진 값을 삽입하여 정렬하는 방법으로 점진적으로 해결하는 형태입니다.

shell은 이게 아니라 사람이름입니다~

예를 들어 간격이 10이라면 0, 10, 20, 30...의 요소를 뽑아 이 요소간의 삽입정렬을 합니다. 다음으로 1을 더해 1, 11, 21, 31...의 요소 간 삽입정렬을 하는 식으로 반복하여 9, 19, 29, 39 ...의 요소를 마지막으로 삽입정렬을 합니다.

다음 과정으로 간격을 적당히 줄이는데 처음 간격인 10을 2로 나누어 새로운 간격이 5라하면 0, 5, 10, 15, 20...요소에 대해 삽입정렬을 수행하는 식으로 4, 9, 14, 19, 24...까지의 요소를 마지막으로 삽입정렬 합니다. 

이런 식으로 간격이 1이 될 때까지 줄여서 반복 삽입정렬을 수행하게 되는데 간격이 1이 되면 삽입정렬과 동일한 알고리즘이 되므로 거의 다 정렬이 되어 있는 상태로 매우 빠른 속도로 삽입정렬을 할 수 있습니다.

 

쉘정렬 알고리즘 의사코드 (Pseudo code)는 아래와 같습니다.

1. h 의 초기값을 구한다.
2. h가 1보다 작으면 끝난다.
3. i = 0
4. i >=h 이면 7로 간다.
5. h+i 요소에 대해 삽입 정렬을 한다.
6. i++, 4로 간다.
7. h의 다음 값을 구하고 2로 간다.

다음과 같이 문자배열이 있다고 가정하면, 첫 번째 수행에서는 배열의 크기가 14이고 h의 초기값을 배열의 크기/2로 잡아 7로 설정하면 그림과 같이 각 7번째 요소끼리 삽입정렬을 수행합니다.

두 번째 수행은 첫 번째 수행의 간격인 7을 2나누면 h값은 3이 됩니다. 그러면 다음과 같이 각 3번째 요소끼리 삽입정렬을 수행합니다.

세 번째 수행은 위의 방법대로 간격을 계산하면 h값은 1이 되어 전체 배열에 대한 삽입정렬을 수행하므로 앞선 포스팅의 삽입 정렬과 완전 동일합니다. 이 단계에서는 어느 정도 정렬이 되어 있는 배열이므로 빠른 정렬을 하게 됩니다.

 

다음은 C언어로 작성한 쉘정렬 소스입니다.

#include <stdio.h>
#include <string.h>

void print_data(char a[], int n);

void shell_sort(char a[], int n)
{
    int i, j, k, h, v;
    for (h = n/2; h > 0; h /=2) {
        for (i=0; i < h; i++) {
            for (j = i+h; j < n; j += h) { /* h간격에 있는 데이터 삽입 정렬 */
                v = a[j];
                k = j;
                while (k > h-1 && a[k-h] > v) {
                    a[k] = a[k-h];
                    k -= h;
                }
                a[k] = v;
                printf ("h= %d step>>>", h);
                print_data(a,n);
            }
            print_data(a, strlen(a));
        }
    }
    
}

void print_data(char a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    char data[] = "learnalgorithm";
    print_data(data, strlen(data));
    shell_sort(data, strlen(data));
}

아래는 수행 결과 입니다. 

PS C:\CS> .\shell_sort.exe
l e a r n a l g o r i t h m 
g e a r n a l l o r i t h m 
g e a r n a l l o r i t h m 
g e a r n a l l o r i t h m 
g e a i n a l l o r r t h m 
g e a i n a l l o r r t h m
g e a i n a l l o r r t h m
g e a i n a l l o r r t h m
g e a h n a i l o l r t r m
g e a h l a i m o l n t r r
g e a h l a i m o l n t r r
a a e g h i l l m n o r r t

정리하자면 쉘정렬은 삽입정렬의 인접요소간 자료교환의 비효율성을 개선하기 위해 제안된 알고리즘입니다.  일정 간격이 떨어진 부분 배열간 정렬을 수행하여 어느 정도 정렬이 된 상태로 만듭니다. 마지막 단계에서는 정렬이 어느 정도 되어 있어 삽입정렬의 빠른 수행효과를 얻어낼 수 있습니다.

 

지금까지 기본 정렬 알고리즘에 대해서 살펴봤습니다. 다음 시간부터는 조금 더 성능이 좋은 정렬 알고리즘에 대해 알아보도록 하겠습니다.