셸 정렬 (shell sort)

셸(shell) 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완한 정렬 알고리즘이다.

참고: 단순삽입정렬

//기본 셸 정렬
static void shellSort(int[] a, int n) {
    //h : 요소사이의 간격을 뜻한다. h 간격의 요소를 비교하여 삽입정렬을 진행한다.
    for (int h = n / 2; h > 0; h /= 2) //h는 계속 2로 나눈 몫이 된다.  ex) h = 4, 2, 1
        for (int i = h; i < n; i++) { //i = 4, 5, 6.. 로 차례로 증가
            int j;
            int tmp = a[i]; //a[4] 값을 임시 저장한다.
            //j = 0부터 시작. a[i-h]값이 tmp보다 클때만 for문을 돈다.
            //증분은 j에서 h값을 빼준다.
            for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
                a[j + h] = a[j]; //복사
            a[j + h] = tmp;
        }
}

위 코드의 문제점은 h 수열이 서로 배수가 될 경우 동일한 요소들끼리만 섞인다는 점이다.

//셸 정렬 개선 버전
//h값 수열을 서로 배수가 되지 않도록 h값을 변경
static void shellSort2(int[] a, int n) {
    int h;
    //h의 초기값을 미리 계산해놓는다.
    //초기값은 너무 크면 의미가 없으므로 배열의 요솟수 n을 9로 나눈 몫을 넘지 않도록 정한다.
    //그리고 h간격을 3배한 후 1을 더하면 요소가 충분히 섞일수 있도록 하는 초기값을 구할 수 있다.
    for (h = 1; h < n / 9; h = h * 3 + 1)
        ;
    
    //h를 3으로 나눈 몫을 가지고 간격이 점차 줄어들어
    for ( ; h > 0; h /= 3) //마지막엔 h가 1이 남게 될 것이다.
        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;
        }

}