[C] 셸 정렬(Shell Sort)

셸 정렬(Shell Sort)

---

셸 정렬?

셸 정렬은 Donald Shell이라는 분이 창안해서 이름이 셸 정렬이 되었다고 합니다.

셸 정렬은 삽입정렬의 단점을 보완하기 위해 등장한 정렬방법입니다.

(단점 예 : 내림차순으로 정렬된 항들을 오름차순으로 정렬하려면 모든 항을 계산 해야 하는 점)

효율 적인 삽입 정렬을 위해 특정 기준으로 사전에 정렬을 수행한 후에 삽입정렬을 수행합니다.

사전에 진행하는 정렬은 특정 기준을 정해서 진행합니다.

어떠한 방법?

저는 길이가 10개인 배열을 2로 나누면서 기준을 잡았습니다.

총 크게 3번 정렬을 진행 했습니다.

10/2 = 5, 5/2 = 2(int형이므로 2.5에서 버림처리), 2/2 =1

아래와 같이 배열에 10개의 인자가 있을 때

1번째 정렬은 5개씩 나눠서 각각 비교해서 정렬 합니다.

각 대응되는 항의 크기를 비교해서 정렬을 하면 아래와 같습니다.

2번째 정렬은 2개 전 항과 비교하며 정렬합니다.

2개의 항씩 정렬하고나면 아래와 같습니다.

마지막으로 3번째 정렬은 전체 항을 삽입 정렬 합니다.

---

배열을 이용한 셸 정렬 예제

셸 정렬 함수

첫번째 for문 : 5개, 2개, 1개씩 비교를 위한 기준 for문,

두번째 for문 : 기준까지만(5,2,1) 반복하기 위한 for문

세번째 for문 : 위 기준대로 반복하는 for문

while문 : 위 그림들 처럼 비교했을 때 작을경우 삽입하는 동작을 수행

void shell_sort(int array[], int size){

for(int i=size/2; i>0; i /=2){

for(int j=0; j<i; j++){

for(int k=i+j; k<size; k+=i){

int l = array[k];

int m = k;

while(m>i-1 && array[m-i] > l){

array[m]=array[m-i];

m -= i;

}

array[m] = l;

}

}

printf("i=%d || ",i);

print_array(array,size);

}

}

배열 출력 함수

void print_array(int array[], int size){

for(int i=0; i<size; i++){

printf("%-4d",array[i]);

}

printf("\n");

}

실행 함수

정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.

void main(){

int array[] = {11,10,33,22,55,9,99,81,15,27};

int size = sizeof(array)/sizeof(int);

printf("########### Sorting before ###########\n");

print_array(array, size);

printf("######################################\n");

shell_sort(array, size);

}

실행 결과

---

참고 : C로 배우는 알고리즘 (이재규)

위키백과(셸 정렬)

---

관련 포스팅

[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)