1. 원 리
주어진 입력 리스트를 적당한 매개 변수의 값만큼 서로 떨어진 레코드들과 비교하여 교환하는 과정을
매개 변수 값을 바꾸어가며 되풀이 하는 것. 이 때 서로 떨어져 있는 레코드들은 하나의 부분 리스트를
구성하며 이들은 다른 정렬 방법(보통 삽입 정렬)에 의해 개별적으로 정렬된다.
매개변수의 값은 흔히 증분(increment)이라고 부르는데 먼저 적절한 값을 선택한 후에 점차 감소시켜
가면서 셸 정렬을 수행하고 매개 변수의 값이 1 이 될 때 종료한다.
[예제] inc = 8 이고 입력 레코드를 (8,3,5,6,2,1,7,4)라고 할 때 셸 정렬을 수행한 과정 및 결과.
초기 상태 : 8,3,5,6,2,1,7,4
증분 = 5
┌─────────┐
┌─┼───────┐ │
┌─┼─┼─────┐ │ │
│ │ │ │ │ │
8 3 5 6 2 1 7 4
부분리스트 : {8,1}, {3,7}, {5,4}, {6}, {2} (각 부분들을 개별 비교하여 위치바꿈 한다)
정렬 후 : 1,3,4,6,2,8,7,5
증분 = 3
┌─────┐
┌─┼───┬─┼───┐
┌─┼─┼─┬─┼─┼─┐ │
│ │ │ │ │ │ │ │
1 3 4 6 2 8 7 5
부분리스트 : {1,6,7}, {3,2,5}, {4,8} (역시, 각 부분들을 개별 비교 정렬 한다)
정렬 후 : 1,2,4,6,3,8,7,5
증분 = 1
┌─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │
1 2 4 6 3 8 7 5
부분리스트 : {1,2,4,6,3,8,7,5}
정렬 후 : 1,2,3,4,5,6,7,8
2. 셸 정렬을 수행하는 함수
#define INFO_LEN 256
#define MAX_REC 256
struct sList {
int count;
struct item {
char info[INFO_LEN] ;
int key ;
} rec[MAX_REC] ;
}
void Shell_Sort (struct sList *LIST)
{
int inc, first;
inc = LIST->count;
while (inc != 1) {
inc = inc/3 + 1;
for (first = 0 ; first < inc ; first++)
Sort (first, inc, LIST) ;
/* Sort()함수는 적절한 내부정렬방법 사용해서 직접 구현해야 합니다 (단순크기비교) */
}
}
※ Shell Sort 는 증분(increment)의 크기를 어떻게 잡느냐에 따라 실행 속도에 영향을 줍니다.
EOF : 2007-04-19 (Poseidon)
|
|
|
