c언어 - 쉘 정렬 (Shell's Sort)

쉘정렬은 삽입 정렬의 개선판으로 생각하고 접근하면 편하다. 그러므로 사전지식으로 삽입정렬을 이해하고 있어야한다.

간단하게 삽입 정렬은 한번에 하나의 값만 바꿔가며 정렬하는 알고리즘이다.

만약 8,2,4,5,1,9 라는 배열이 있다고 가정하고 삽입 정렬을 하면 단1회 만으로 1,2,4,5,8,9 로 정렬이 된다.

이런 장점을 키운 정렬이 쉘 정렬이다.

*참고 - 삽입 정렬

 

쉘 정렬은 갭의 크기가 줄어들면서 정렬되는 알고리즘이다.

예를들어 n개의 값을 가지고 있는 배열이 있다고 가정하면, 처음 갭은 n/2인 값으로 그 후의 갭은 전의 갭/2 인 값으로 정렬해 나간다.

*갭은 짝수보다 홀수가 좋다, 갭이 짝수일때 + 1을 해서 홀수를 만들어주자

*c언어에서 정수인 변수의 소숫점은 무시된다. ex) 1.9 => 1 

 

아래 배열을 10개의 값을 가지고 있는 배열을 볼 수 있다.

9

6

5

8

10

1

3

7

4

2

 

처음의 갭의 값은 (10/2)인 5이다.

9					1
	6					3
		5					7
			8					4
				10					2

5의 값 만금 간격을 띈 배열의 값들만 비교하게된다.

1					9
	3					6
		5					7
			4					8
				2					10

1

3

5

4

2

9

6

7

8

10

 

두번째 갭은 (5/2)+1 인 3이 된다.

1			4			6			10
	3			2			7
		5			9			8

3의 값 만금 간격을 띈 배열의 값들만 비교하게된다.

1			4			6			10
	2			3			7
		5			8			9

1

2

5

4

2

8

6

7

9

10

세번째 갭은 3/2 인 1이 된다.

1

2

5

4

3

8

6

7

9

10

각각 삽입 정렬로 정렬된다.

1

2

3

4

5

6

7

8

9

10

정렬 끝

 

이런식으로 진행이된다.

 

---

핵심 알고리즘

---

while(1) {
	if(gap%2==0)
		gap++;
	for(i=gap; i<n; i++) {
		key=arr[i];
		for(j=i-gap;j>=0;j=j-gap) {
			if(key < arr[j]) 
				arr[j+gap] = arr[j];
			else
				break;
		}
	arr[j+gap] = key;
	}
   	if(gap == 1)
		break;
	gap=gap/2;
}

코드

---

#include<stdio.h>
void ShellSort(int *arr, int n);

int main() {
    int arr[] = {9,6,5,8,10,1,3,7,4,2};
    ShellSort(arr,10);
    return 0;
}

void ShellSort(int *arr, int n) {
    int gap,c=0;
    int key,j,i=0;
    gap = n/2;

    while(1) {
        if(gap%2==0)
            gap++;
        for(i=gap; i<n; i++) {
            key=arr[i];
            for(j=i-gap;j>=0;j=j-gap) {
                if(key < arr[j])
                    arr[j+gap] = arr[j];
                else
                    break;
            }
        arr[j+gap] = key;
        }
        if(gap == 1)
            break;
        gap=gap/2;
    }
    for(c=0;c<n;c++){
        printf("%d ",arr[c]);
    }
}