Shell Sort (쉘 정렬)
2011. 2. 26. 17:01
알고리즘
쉘 정렬은 삽입 정렬의 단점을 보완하기 위해서 Donald Shell이 1958년 고안한 방법이다.
삽입 정렬은 Array 전체에 대해서 정렬을 수행하게 된다.
최악의 경우, 다시말해서 오름차순 정렬을 해야하는데, Array가 내림차순 정렬이 되어있는 경우
연산이 많아지게 될 수 밖에 없다.
쉘 정렬의 기본적인 아이디어는 삽입 정렬을 하기 전에 정리를 해놓자는 것이다.
그렇다면, 어떻게 정리할 것인가?
삽입 정렬은 모든 원소에 대해서 검사를 하지만,
쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고,
그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다.
간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다.
하지만 이미 Array가 어느정도 정리 되어 있기 때문에, 삽입 정렬에 소모되는 연산이 줄어드는 것이다.
설명이 난해할 것 같아, 예제를 통해 설명을 이어나가도록 하겠다.
45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43
위와 같은 정렬이 있다. 우리는 간격을 5, 3, 1로 놓고 삽입 정렬을 시작할 것이다.
간격이 5일 경우, 같은 묶음 끼리 같은 색으로 표시해 보면,
45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43
이제 각각의 묶음에 대해서 삽입 정렬을 한다. 즉,
묶음1: 45, 44, 77
묶음2: 39, 33, 68
묶음3: 98, 28, 11
묶음4: 15, 40, 43
묶음5: 52, 38
위와 같은 5개의 묶음을 가지고 각각에 대해서 삽입 정렬을 하는 것이다.
정렬된 Array의 모습은 아래와 같다.
44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43
물론 각각의 묶음의 위치는 변동이 없다.
이제 3의 간격을 가지고 새로운 묶음을 만들어 보자.
44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43
묶음1: 44, 15, 39, 52, 98
묶음2: 33, 38, 28, 77, 43
묶음3: 11, 45, 40, 68
이제 위 묶음들에 대해서 삽입 정렬을 수행한다.
15, 28, 11, 39, 33, 40, 44, 38, 45, 52, 43, 68, 98, 77
이제 대략적으로 작은 숫자들은 앞쪽, 큰 숫자들은 뒤쪽에 모여있는것을 볼 수 있다.
이제 묶음을 만들 필요 없이 전체 Array에 대해서 삽입 정렬을 하는 것으로 쉘 정렬이 마무리된다.
간격을 어떻게 설정할 것인가
위에서는 임의로 5, 3, 1이라는 간격을 사용했다.
이 간격을 어떻게 설정해 줄 것인가에 대한 문제가 상당히 고심이 되는 부분이 아닐 수 없다.
일단, 배열의 길이를 토대로 설정하는 방법을 생각해 볼 수 있다.
배열의 길이를 N이라고 잡았을 때,
첫번째 간격을 N/2, 두번째 간격을 N/4 ... 와 같이 잡는 방법이 있다.
(물론 각각의 간격을 int에 저장하면 소수점 이하는 소실된다. 길이가 23이라면 23, 11, 5, 2, 1 과 같이 될 것이다.)
N/3, N/9 ... 와 같이 잡을 수도 있다.
(길이가 23이라면, 23, 7, 2, 1 과 같이 된다.)
Donald Shell은 처음에 간격을 2^k, (k는 0 이상의 자연수) 혹은 2^k-1로 잡았으며,
Marcin Ciura의 연구에 의하면 1, 4, 10, 23, 57, 132, 301, 701, 1750 ... 과 같은 간격을 사용하는 것이
연산 시간을 많이 줄인다고 한다.
아래의 코드는 간격을 N/3 - 1로 잡고 코딩을 한 것이다.
코드
#include <stdio.h>
void shell_sort(int num[],int len);
void tracer(int num[],int len);
int main(void){
int testArr[] = {485,241,454,325,452,685,498,890,281};
int len = sizeof(testArr)/sizeof(int);
shell_sort(testArr,len);
}
void shell_sort(int num[],int len){
int i,j,m,tempINT;
int k = len;
do {
k = k/3 + 1; // 다음 간격을 k/3 + 1로 구함
printf("간격 k = %d\n",k); // 간격을 보여준다.
for (m=0; m<k; m++){ //m은 각 묶음의 첫 인덱스가 된다.
for (i=m+k; i<len; i+=k){
// 삽입정렬은 첫번째 원소를 정렬된 것으로 간주함
// 따라서 첫 인텍스는 m+k가 된다.
tempINT = num[i];
for(j=i-k; num[j] > tempINT && j>=0; j-=k){
num[j+k] = num[j];
}
num[j+k] = tempINT;
// 나머지 부분은 삽입 정렬과 같다.
}
}
tracer(num,len);
} while (k != 1); // k가 1이 되면, 더 이상 정렬할 필요 없음
}
void tracer(int num[],int len){
int i;
for(i=0;i<len;i++){
printf("%d\t",num[i]);
}
printf("\n\n");
}
결과
