셸 정렬(shell sort)

• 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘
• 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법
  • 퀵 정렬이 고안되기 전까지 가장 빠른 알고리즘으로 알려져 있었다.
• 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 '4-정렬'이라고 한다.
• 4-정렬 → 2-정렬 → 1-정렬을 적용하면 정렬을 마치게 된다.
  • 4-정렬, 2-정렬로 조금이라고 정렬에 가까운 상태로 만든 다음 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마친다.
  • 여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서이다.
• 셸 정렬 과정에서 수행하는 각각의 정렬을 'h-정렬'이라고 한다.

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

 

• 그룹별 정렬 시 요소가 충분히 섞여 효율적인 정렬을 할 수 있도록 h 값이 서로 배수가 되지 않도록 개선한다.
• 시간 복잡도는 O(n^1.25)
• 그러나 이 알고리즘도 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.

//셸정렬(버전 2)
static void shellSort(int[] a, int n) {
    int h;
    for (h = 0; h < n / 9; h = h * 3 + 1)    //h의 초깃값을 구한다
        ;
    
    for (; h > 0; h /=3) {
        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;
        }
    }
}