쉘 정렬은 삽입 정렬의 단점을 보완할 수 있는 좋은 알고리즘이다.
심지어 구현 난이도도 낮으면서 성능까지 준수한 알고리즘이다!
먼저 삽입 정렬은 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보여준다.
하지만 그렇지 않은 경우에는 속도가 매우느린데, 그 이유가 삽입 정렬이 바로 인접한 요소와 비교를 하기 때문이다. (array[j - 1] > array[j])
따라서 배열이 만약 역순인 상태라면 가장 작은 키값이 제일 뒤에 있기 때문에 N번의 비교와 이동이 필요하게 된다.
쉘 정렬은 이 문제를 해결하기 위해서 h만큼의 간격으로 떨어진 레코드를 삽입 정렬하는 방법이다.
쉘 정렬의 전략
인접한 요소만을 교환하는 삽입 정렬의 단점을 극보갛기 위해서 쉘 정렬은 뚝 떨어진 요소들을 교환한다.
쉘 정렬의 기본 개념은 정ㄹ열한 배열에서 h간격의 요소들만 뽑아서 삽입 정렬을 하는것이다!
예를 들어서 h가 10이라면 0, 10, 20, 30, 40...의 요소들만 뽑아서 이 요소들간의 삽입정렬을 한다. 그 다음으로 1씩을 더해서 1, 11, 21, 31, 41...의 요소들을 뽑아서 삽입정렬을 한다. 또 그 다음으로는 2, 12, 22, 32, 42...의 요소를 뽑아서 정렬하고 마지막으로 9, 19, 29, 39, 49...의 요소를 뽑아서 삽입정렬을 한다.
그 다음 과정으로는 h를 적당한 크기로 줄이는데, 2로 나눠서 h가 5라고 가정하자.
그러면 0, 5, 10, 15, 20, 25, 30...과 같은 요소들만 뽑아서 삽입 정렬하고 다음으로 1, 6, 11, 16, 21, 26, 31...과 같은 요소들을 뽑아서 삽입정렬한다. 마지막으로 4, 9, 14, 19, 24, 29, 34...과 같은 요소를 뽑아서 삽입정렬 한다.
이 과정을 계속 반복하는게 바로 쉘 정렬이다.
이때 h가 1일땐 일반적인 삽입정렬과 동일한 동작을 하게되고, h가 1보다 작을경우는 쉘 정렬을 종료하게 된다.
또한 h가 10이라면, h보다 작은 9까지만 숫자를 증가시켜서 비교한다. 즉 (0, 10, 20) 부터 시작해서 (9, 19, 29) 까지만 비교하고 이후에는 h를 줄이는 과정을 거친다.
반약 h와 동일한 값을 증가시키면 (0, 10, 20) 부터 시작해서 (10, 20, 30)이라는 값을 비교하게되고 이는 array를 초과하는 우를 범할수도 있음과 동시에 이미 비교를 해둔것들이기도 하다.
즉 아래와 같은 시퀀스를 가진다.
- h의 초기값을 구한다.
- h가 1보다 작으면 종료한다.
- i = 0 부터 시작한다.
- i가 h보다 크거나 같으면 7번으로 간다.
- (h + i) 요소들에 대해서 삽입 정렬을 한다.
- i를 1증가 시키고 4번으로 간다.
- h의 다음 값을 구하고 2번으로 간다.
C로 구현한 쉘 정렬
void shell_sort(int array[], int length) {
int target;
int target_index;
for(int h = length / 2; h > 0; h /= 2) {
for(int i = 0; i < h; i++) {
for(int j = i + h; j < length; j += h) {
target = array[j];
target_index = j;
while(target_index > h - 1 && array[target_index - h] > target) {
array[target_index] = array[target_index - h];
target_index -= h;
}
array[target_index] = target;
}
}
}
}h가 추가된것과 4중 루프가 된것을 제외하면 삽입 정렬과 비슷한 느낌이라는걸 알 수 있는데, 실제로 h가 1일때는 삽입 정렬과 로직이 동일하다.
위 코드를 보듯이 4중 루프로 구성되어 있어서 속도가 매우 느릴거라고 생각된다. O(N^4)처럼 보인다랄까!?
하지만 쉘 정렬은 속도 측면에서 아주아주 준수한 성능을 보여준다.
실제로 이미 정렬이 된 배열, 난수 배열, 반쯤 정렬된 배열, 역순 배열 모든 케이스에서 준수하다.
쉘 정렬은 h를 정하는 방법에 따라 알고리즘 성능이 달라지기 때문에 일률적으로 성능을 나타낼수 없지만 일반적으로 O(N(logN)^2) 이나 O(N^1.25) 정도의 성능을 가진것으로 나온다.
실제로 O(NlogN) 성능을 보이는 알고리즘에 비해서 속도가 조금 떨어지지만 10,000개 이하의 자료 정도면 오히려 좋을수 있다.
추가적인 메모리가 필요한것도 아니고 구현도 더 간단하다.
쉘 정렬 개선
쉘 정렬의 경우 h가 성능을 좌지우지하는 핵심인데, 이를 적절한 값으로 설정함으로 인해서 성능을 개선할 수 있다.
Robert Sedgewick이라는 분께서 말씀하시길 hn = 3*hn-1+1, h1 = 1. 즉 1, 4, 13, 40, 121, 364, 1093... 과 같은 숫자가 가장 효율적이라고 했다.
이 숫자를 이용해서 소스코드를 개선하면 아래와 같다.
void shell_sort2(int array[], int length) {
int h;
int target;
int target_index;
for(h = 1; h < length; h = 3 * h + 1);
for(h /= 3; h > 0; h /= 3) {
for(int i = 0; i < h; i++) {
for(int j = i + h; j < length; j += h) {
target = array[j];
target_index = j;
while(target_index > h - 1 && array[target_index - h] > target) {
array[target_index] = array[target_index - h];
target_index -= h;
}
array[target_index] = target;
}
}
}
}먼저 for(h = 1; h < length; h = 3 * h + 1); 해당 부분은 정렬해야할 배열의 길이내에서 가장 효율적인 h의 최대값을 찾는 과정이다.
그리고 h의 for 루프에서 증감 부분이 h /= 3 이라고 되어있어서 이상해보일 수 있다.
수학적으로 접근해보면 hn-1 = (hn - 1) / 3 이렇게 표시해야한다. 하지만 이를 풀어쓰면 (hn / 3) - (1 / 3) 이다.
C언어에서 1/3은 소숫점을 쓰지않는 상수는 정수로 취급하기에 0으로 취급된다. 따라서 h = h / 3이 된다.
결과적으로 동일한 조건에서 시간을 측정하면 20%정도 속도를 개선시킬 수 있다고 한다.
아래는 time.h를 이용해서 비교해본 결과인데, 기본적인 쉘 정렬도 빠른데 h를 개선한 쉘 정렬은 더 빠르다...ㅋㅋ
Before shell sorting.
T O L E A R N S O R T A L G O R I T H M
After shell sorting.
A A E G H I L L M N O O O R R R S T T T
[run time: 0.000004]
After shell sorting2.
A A E G H I L L M N O O O R R R S T T T
[run time: 0.000000]전체 코드
//
// main.c
// ShellSort
//
// Created by 박재현 on 2024/06/25.
//
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void print_array(int array[], int length) {
for(int i = 0; i < length; i++) {
printf("%c ", array[i]);
}
printf("\n");
}
void shell_sort(int array[], int length) {
int target;
int target_index;
for(int h = length / 2; h > 0; h /= 2) {
for(int i = 0; i < h; i++) {
for(int j = i + h; j < length; j += h) {
target = array[j];
target_index = j;
while(target_index > h - 1 && array[target_index - h] > target) {
array[target_index] = array[target_index - h];
target_index -= h;
}
array[target_index] = target;
}
}
}
}
void shell_sort2(int array[], int length) {
int h;
int target;
int target_index;
for(h = 1; h < length; h = 3 * h + 1);
for(h /= 3; h > 0; h /= 3) {
for(int i = 0; i < h; i++) {
for(int j = i + h; j < length; j += h) {
target = array[j];
target_index = j;
while(target_index > h - 1 && array[target_index - h] > target) {
array[target_index] = array[target_index - h];
target_index -= h;
}
array[target_index] = target;
}
}
}
}
int main(int argc, const char * argv[]) {
int length;
int *array;
int *array2;
char *str = "TOLEARNSORTALGORITHM";
clock_t start, end;
length = (int)strlen(str);
array = (int *)malloc(sizeof(int) * length);
array2 = (int *)malloc(sizeof(int) * length);
for(int i = 0; i < length; i++) {
array[i] = str[i];
array2[i] = str[i];
}
printf("Before shell sorting.\n");
print_array(array, length);
printf("\nAfter shell sorting.\n");
start = clock();
shell_sort(array, length);
end = clock();
print_array(array, length);
printf("[run time: %f]\n", (float)(end - start)/CLOCKS_PER_SEC);
printf("\nAfter shell sorting2.\n");
start = clock();
shell_sort2(array, length);
end = clock();
print_array(array, length);
printf("[run time: %f]\n", (float)(end - start)/CLOCKS_PER_SEC);
return 0;
}실행 결과
