[Data Structure] 셸 정렬(Shell's sort)

---

셸 정렬

 

 

어느 정도 정렬된 상태에서 삽입 정렬이 효율적인 것에 착안하여 만들어진 정렬 방법이다. 삽입 정렬은 요소들이 이웃한 위치와만 교환이 이뤄지기 때문에 특정 값이 멀리 이동하는 데에 많은 교환이 필요하다. 이때 요소를 멀리 떨어진 위치와 교환할 수 있다면 더 적은 교환으로 요소를 이동시킬 수 있을 것이다. 즉 삽입 정렬에서 한 칸이면 간격을 늘린다면 더 멀리 떨어진 요소를 효율적으로 옮길 수 있다는 것인데, 이런 방식의 정렬을 사용하는 것이 셸 정렬이다.

먼저 정렬 대상 리스트를 일정 간격의 부분 리스트로 나누고 나뉜 각 부분 리스트를 삽입 정렬한다. 정렬이 끝난 후 다시 간격을 줄이고 정렬하고, 반복하여 간격이 1인, 즉 원래의 삽입 정렬과 똑같이 될 때까지 부분으로 나누고 정렬한다. 마지막 간격이 1인 삽입 정렬이 끝나면 전체 리스트가 정렬된다.

설명한 바와 같이 정렬 간격이 중요한데, 정렬 간격에 따라 효율이 다르게 나온다. 간격만 잘 선택하면 굉장히 효율적 정렬이다. 그러나 간격에 대한 특별한 공식은 없다. 실험적으로 1, 4, 10, 23, 57, 132, 301, 701 정도의 효율적 간격이 발견되었다고는 한다. 편한 방법은 정렬 대상의 사이즈의 반으로 시작하여 계속 반씩 나누는 것이다. 이때 짝수가 나온다면 보정하여 홀수로 만들어준다.

 

---

예시

 

예를 들어 위와 같은 리스트를 정렬한다고 해보자.

먼저 리스트 길이의 반인 5를 간격으로 설정해주고 아래와 같이 각 나뉜 부분을 삽입 정렬로 정렬해준다.

$$ \vdots $$

정렬이 끝났다면 다시 간격을 설정하고 또 삽입 정렬로 정렬해준다.

$$ \vdots $$

간격이 1이 되어 일반적인 삽입 정렬을 실시하면 아래와 같이 정렬된다.

최악의 경우에는 삽입 정렬와 차이가 없기 때문에 삽입 정렬의 최악의 경우와 같이 $ \mathcal{O} (n^2) $ 의 시간복잡도를 가지지만, 평균적으로는 $ \mathcal{O} (n^{1.5}) $ 의 시간복잡도를 가지는 효율적인 정렬 방법이다.

 

---

구현 | C

 

void shell_sort(int list[], int n) {
    for (int gap = n / 2; gap > 0; gap = gap / 2) {
        if (gap % 2 == 0) {
            gap++;
        }
        for (int i = 0; i < gap; i++) {
            for (int j = i + gap, k; j <= n - 1; j = j + gap){
                int key = list[j];
                for(k = j - gap; k >= i && key < list[k]; k = k - gap) {
                    list[k+gap] = list[k];
                }
                list[k+gap] = key;
            }
        }
    }
}