셸(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;
}
}
댓글 없음:
댓글 쓰기