shellSort.c

#include <stdio.h>

/**
 * 쉘 정렬
 * 
 * 배열을 부분 배열로 나눔
 * -> 이때, 부분 배열은 각 부분 배열의 첫 인덱스 원소부터 h만큼의 간격으로 원소들을 선택해서 구성
 * -> 각 부분 배열별로 삽입 정렬을 수행
 * -> 간격 h를 줄여 가면서 위와 같은 정렬을 반복 수행
 */
int solution(int a[], int n) {
    int result = 0;

    int h = 1; // 부분 배열 간 간격. 부분 배열은 h만큼의 간격에 있는 원소들을 원소로 가진다.
    int value = 0; // 자리 찾을 값 (삽입할 값)
    int i, j = 0; // i: 자리 찾을 값 인덱스, j: 현재 위치 
    
    do {
        h = 3*h + 1; // n보다 작은 최대 간격 찾기
    } while (h < n); // n을 갓 넘은 h값
    do {
        h = h / 3; // 부분 배열의 간격 줄여가면서 정렬 수행. 최종적으로는 간격이 1인 부분 배열을 결과로 산출하게 됨.
        for (i = h; i < n; i++) { // h 만큼을 띄워서 초깃값 설정. 이를 통해 h 간격의 원소들끼리 비교할 수 있게됨 
            value = a[i]; // 자리를 찾을 값
            j = i; // 현재 자리

            while (a[j-h] > value) { // 자리를 찾을 값과 h 전의 값을 비교해서 순서가 안 맞다면 정렬
                a[j] = a[j-h]; //
                j -= h; // 이를 통해 간격 h마다 대응되는 원소끼리 비교할 수 있게 됨
                if (j < h-1) break; // 리스트의 하한치를 넘어가서 j가 설정되면 탈출
            }
            a[j] = value; // 정해진 위치에 자리를 찾는 값을 대입
        }
    } while (h > 1); // 간격이 1보다는 클 때까지 수행

    return result;
}

void main() {
    int a[] = {30, 50, 15, 60, 35, 10, 40, 45, 5, 25, 55, 20};
    int n = 12;

    int sol = solution(a, n);
}