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

셸 정렬의 개념

셸 정렬이란 Donald L. Shell이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안하여 삽입정렬을 보완한 알고리즘이다.
삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다.
즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 하지만 셸 정렬은 삽입 정렬과 다르게 전체 리스트를 한 번에 정렬하지 않는다.

셸 정렬의 과정은 다음과 같다.

1. 리스트 전체를 $h_0$ 간격의 부분 리스트들로 나눈다. 이때 $h_0$는 일반적으로 리스트의 길이의 절반으로 설정한다.
2. 일정한 간격으로 나눈 리스트를 각각 삽입 정렬한다.
3. 삽입 정렬한 부분 리스트들을 하나의 리스트로 합친 뒤 다시 나누는데 이때 리스트를 나누는 간격은 $h_0$의 절반으로 설정한다.
4. 부분 리스트들을 다시 삽입 정렬하고 하나의 리스트로 합친다.
5. 이 과정을 $h_0$가 1이 될 때 까지 반복하고 삽입정렬을 실시한다.

시간복잡도

Average

$T(n) = O(n^1.5)$

Worst

$T(n) = O(n^2)$

셸 정렬의 장단점

장점

• 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.
• 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.
• gap sequence가 적절하게 선택되면 시간복잡도가 $O(nlogn)$ 정도로 매우 빨라진다.

단점

• 일반적인 삽입정렬에 비해 구현이 까다롭다.
• 일정 간격을 두고 원소의 교환이 일어나기 때문에 안정적인 정렬 방식이 아니다.
• gap sequence에 영향을 많이 받기 때문에 적절한 k를 설정하는 것이 중요하다.

구현

#include <iostream>

using namespace std;

void shellSort(int arr[], int len) {
    int i, j, temp;
    int gap = len / 2;
    while (gap > 0) {
        for (i = gap; i < len; i++) {
            temp = arr[i];
            j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

int main() {
    int arr[] = { 10,8,6,20,4,3,22,1,0,15,16 };
    int len = sizeof(arr) / sizeof(int);

    cout << "정렬 전: ";
    for (int x : arr)
        cout << x << " ";
    cout << endl;

    shellSort(arr, len);

    cout << "정렬 후: ";
    for (int x : arr)
        cout << x << " ";
    cout << endl;
}