셸 정렬 (Shell Sorting)

Donald L. Shell 이라는 사람이 제안한 방법이다.

삽입 정렬이 어느 정도 정렬된 배열에 대해서는 아주 빠르다는 것에 착안하여 고안한 방법이다.

셸 정렬은 삽입정렬의 보다 빠르다.

삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하는 것이다.

만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야한다.

셸 정렬은 요소들이 멀리 떨어진 위치로도 이동이 가능하다.

삽입 정렬은 전체의 리스트를 한 번에 정렬하는데 비해, 셸 정렬은 그렇지않다.

 

1. 정렬할 리스트를 일정기준에 따라 분류하여 연속적이지 않은 여러 개의 부분리스트를 만든다.

2. 모든 부분 리스트를 삽입 정렬을 이용하여 정렬

3. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든다.

4. 알고리즘을 되풀이한다.

5. 부분 리스트의 개수가 1이 될 때까지 되풀이.

예를 들어 요소의 갯수가 10개이고

10 8 6 20 4 3 22 1 0 15 16 이라는 배열이 있다면

 

입력 리스트의 각 5번째 요소를 추출하여 부분 리스트들을 만든다.

첫 번째 부분 리스트는 10, 3, 16으로 구성되며

두 번재 부분 리스트는 8, 22

..

처럼 구성된다.

다음으로 각 부분 리스트에 대해 삽입 정렬이 수행되며

부분 리스트들이 정렬된 후에는, 전체 리스트 기준으로 일부는 정렬이 됐다고 봐도 무방하다.

이것은 실제로 부분 리스트들을 만들어서 수행하는 것이 아니라, 일정한 간격을 기준으로 삽입 정렬을 수행하는 것 뿐이다.

따라서 추가공간은 필요없다.

간격의 기준은 처음에는 n/2로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 사용한다.

다음 코드에서 shell_sort()의 변수 gap이 간격을 나타낸다. shell_sort()는 gap==1이 될 때까지 gap을 1/2로 줄이면서 반복한다.

이때 부분 리스트의 개수 또한 gap이 된다. 각 부분 리스트에 대해 일정한 간격으로 떨어져 있는 요소들을 삽입 정렬하는 함수인 inc_insertion_sort()를 호출한다.

inc_insertion_sort()는 이전의 삽입 정렬 함수와 비교하여 보면 쉽게 이해할 수 있다.

만약 간격이 짝수이면, 1을 더하는 것이 좋다.

따라서 소스에서도 짝수인 경우 간격에 1을 더한다.

// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
void inc_insertion_sort(int list[], int first, int last, int gap) {

    int key, j;

    for (int i = first + gap; i <= last; i += gap) {
        key = list[i];
        for (j = i - gap; j >= first && key < list[j]; j -= gap)
            list[j + gap] = list[j];
        list[j + gap] = key;
    }

}

void shell_sort(int list[], int n) { // n = size
    for (int gap = n / 2; gap > 0; gap /= 2) {
        if ((gap % 2) == 0) gap++;
        for (int i = 0; i < gap; i++) { // 부분 리스트의 개수는 gap
            inc_insertion_sort(list, i, n - 1, gap);
        }
    }
}

전체 프로그램

정렬하기 전의 배열 상태와 각 회전수에 정렬된 배열 상태를 출력한다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10

// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
void inc_insertion_sort(int list[], int first, int last, int gap) {
    int key, j;
    
    for (int i = first + gap; i <= last; i += gap) {
        key = list[i];
        
        for (j = i - gap; j >= first && key < list[j]; j -= gap)
            list[j + gap] = list[j];
        list[j + gap] = key;
    }
    
    for (int k = first; k <= last; k += gap)
        printf("%d ", list[k]);

}

void shell_sort(int list[], int n) { // n = size
    for (int gap = n / 2; gap > 0; gap /= 2) {
        if ((gap % 2) == 0) gap++;
        printf("< gap = %d >\n", gap);
        for (int i = 0; i < gap; i++) { // 부분 리스트의 개수는 gap
            printf("부분리스트%d 정렬 결과 : ", i+1);
            inc_insertion_sort(list, i, n - 1, gap);
            printf("\n");
        }
    }
}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;
    
    printf("<셸 정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < n; i++) {
        list[i] = rand() % n;
        printf("%d ", list[i]);
    }
    printf("\n");
    
    shell_sort(list, n); // 셸 정렬 호출
    
    printf("최종 정렬 결과 : ");
    for (int i = 0; i < n; i++)
        printf("%d ", list[i]);
    printf("\n");
    system("pause");

}

 

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 40000

// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 ifrst에서 last
void inc_insertion_sort(int list[], int first, int last, int gap) {
    int key, j;
    
    for (int i = first + gap; i <= last; i = i + gap) {
        key = list[i];
        for (j = i - gap; j >= first && key < list[j]; j = j - gap)
        list[j + gap] = list[j];
        list[j + gap] = key;
    }

}

void shell_sort(int list[], int n) { // n = size
    clock_t start = clock(); // 시간재기 시작
    for (int gap = n / 2; gap > 0; gap /= 2) {
        if ((gap % 2) == 0) gap++;
        for (int i = 0; i < gap; i++) { // 부분 리스트의 개수는 gap
            inc_insertion_sort(list, i, n - 1, gap);
        }
    }
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("셸 정렬\n크기 : 40000개\n%.4lf초", diff);
}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;
    
    for (int i = 0; i < n; i++) {
        list[i] = rand() % n;
    }
    
    shell_sort(list, n); // 셸 정렬 호출
    
    printf("\n");
    system("pause");
}

 

삽입 정렬에 비해 셸 정렬은 2가지의 장점이 있다.

1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다.

-> 삽입 정렬에서는 한 번에 한 칸씩만 이동한다. 따라서 교환되는 요소들이 삽입 정렬 보다 최종 위치에 더 가까이 있을 가능성이 높아진다.

2. 부분 리스트는 어느 정도 정렬이 된 상태이다.

-> 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하지만, 더욱 빠르게 수행한다.

삽입 정렬이 거의 정렬된 파일에 대해서는 빠르게 수행되기 때문이다.

셸 정렬의 시간 복잡도는 대략,

최악의 경우에는 이지만

평균적인 경우에는 로 나타난다.