정렬 - 셸 정렬

주빈·2022년 2월 24일

algorithm

목록 보기

9/16

오늘은 셸 정렬에 대해 알아보자.

📘 셸 정렬

셸 정렬(shell sort)은 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알로리즘으로, 도널드 셸(D. L. Shell)이 고안했다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다.

먼저 단순 삽입 정렬의 특징을 정리해보자.

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

✏ 셸 정렬 원리

위의 그림처럼 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 '4-정렬'이라고 한다. 이렇듯 2번째 숫자 1과 4칸 떨어진 6을 교환하고 이 방법을 계속하면 된다.
이렇게하면 아직 정렬을 마친 상태는 아니지만 정렬을 마친 상태에 가까워진다.

'4-정렬'을 마친 상태에서 2칸만큼 떨어진 요소를 모아 두 그룹({7,3,8,4},{1,2,6,5})으로 나누어 '2-정렬'을 수행하면된다.

이렇게 해서 얻은 배열은 좀 더 정렬된 상태에 가까워진다.
마지막으로 '1-정렬'을 적용하면 정렬을 마치게 된다.

셸 정렬은 정렬되지 않은 상태의 배열에 대해 단순 삽입 정렬을 수행하는 것이 아니라 '4-정렬', '2-정렬'로 조금이라도 정렬이 된 상태에 가까운 배열로 만들어 놓은 다음에 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마친다.

✏ 셸 정렬 코드

메서드를 작성해서 알아보자.

static void shellSort(int[] a, int n) {
    for (int h = n / 1; 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;
        }
}

위의 shellSort 메서드가 주요 메서드이다.

증분값 h는 4,2,1 로 변화가 된다.
h값은 n부터 감소시켜 마지막에 1이 된다.

근데 이 h값에는 서로 배수가 되지 않도록 해야하는 규칙이 있다.

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

위의 수열을 거꾸로 살펴보면 1부터 시작하여 3배한 값에 1을 더하는 수열이라는 것을 알 수 있다. 또 h의 초깃값은 너무 크면 효과가 없기 때문에 배열의 요솟수 n을 9로 나눈 값을 넘지 않도록 해야한다.

이 수열을 이용해서 shellSort 메서드를 다시 작성해보자.

static void shellSort(int[] a, int n) {
    int h;
    for (h = 1; h < n / 9; h = h * 3 + 1);  // 1)	

    for (; h > 0; h /= 3)					// 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;
        }
}