[대학교 알고리즘] ShellSort

void ShellSort(int A[ ], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
출력 : A[0:n-1] - 정렬된 배열.*/
int h, i, j, Value;
h = 1; // 간격을 설정해줄 변수
do h = 3 * h + 1; while (h < n); // 일단 크기를 늘린다.
do {
h = h / 3; // h는 이미 n보다 큰 수 이기때문에 한번 나누어준다.
for (i=h, i<n; i++) { // i = h 부터 시작하지만 큰 반복문에서 h값은 점점 줄어들기 때문에 전체적으로 반복하게 된다.
Value = A[i]; // 현재의 기준값을 저장
j = i; // 인덱스 일치
while (A[j-h] > Value) { // 처음엔 A[0] 인덱스와 비교 그후에 1씩 증가하는것을 볼 수 있다.
A[j] = A[j-h]; // 삽입정렬과 방법은 같다. 거리가 다르다.
j -= h; // i 값이 h값보다 커지게 되는 순간에는 자신의 아래쪽 간격으로 비교를 할 수도 있다.
if (j <= h-1) break;
}
A[j] = Value; // 만약 비교하여 자리가 바뀌었다면 그자리에 넣어준다.
}
} while (h > 1); // h간격이 1일때까지 실행을 마친후에 종료된다.
}