CS/알고리즘
알고리즘 - 쉘 정렬(Shell's Sort)
clamp
2022. 4. 5. 14:12
쉘 정렬은 삽입 정렬의 개선판. 삽입 정렬을 이해하고 있어야 한다.
삽입정렬
알고리즘 - 삽입 정렬(InsertionSort)
삽입 정렬) 두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘. 해당 배열을 오름차순으로
clamp-coding.tistory.com
쉘 정렬)
쉘 정렬은 갭의 크기가 줄어들면서 정렬되는 알고리즘이다.
예를 들어 n개의 값을 가지고 있는 배열이 있다면, 처음 gap은 n/2인 값 gap = 10, 그 후 갮은 gap/2 로 정렬해 나간다.
*갭은 짝수보다 홀수가 좋다. 갭이 짝수일 경우 +1을 해서 홀수로 만들어 주는게 좋다.
*C언어에서 Int 자료형의 소숫점은 무시된다.
아래의 배열 10개를 정렬해본다
| 5 | 4 | 7 | 1 | 9 | 10 | 6 | 8 | 3 | 2 |
초기 gap = 10/2(n/2) -> 5
| 5 | 10 | ||||||||
| 4 | 6 | ||||||||
| 7 | 8 | ||||||||
| 1 | 3 | ||||||||
| 9 | 2 |
표의 한 라인에는 5칸씩 차이나는 숫자들끼리 넣어놨다.
5(gap)칸 차이가 나는 값 들끼리 비교를 하고 정렬한다.
| 5 | 10 | ||||||||
| 4 | 6 | ||||||||
| 7 | 8 | ||||||||
| 1 | 3 | ||||||||
| 2 | 9 |
자리교환이 일어난 부분
1회전 결과
| 5 | 4 | 7 | 1 | 2 | 10 | 6 | 8 | 3 | 9 |
2번째 갭은 (5/2)+1 = 3
| 5 | 1 | 6 | 9 | ||||||
| 4 | 2 | 8 | |||||||
| 7 | 10 | 3 |
gap(3)씩 간격을 둔 요소들 끼리 비교를 한다.
| 1 | 5 | 6 | 9 | ||||||
| 2 | 4 | 8 | |||||||
| 3 | 7 | 10 |
자리교환이 일어난 요소들
2회전 결과
| 1 | 2 | 3 | 5 | 4 | 7 | 6 | 8 | 10 | 9 |
3번째 gap은 3/2인 1이 된다.
이 후엔 각각 삽입 정렬로 정렬된다.
| 1 | 2 | 3 | 5 | 4 | 6 | 7 | 8 | 9 | 10 |
정렬 끝
이런식으로 진행된다.
코드
void shellsort(double arr[], int N)
{
int gap, c = 0;
int key, j, i = 0;
gap = N / 2; //시작 gap은 N의 절반
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;
}
}실행 결과
해당 자료는 랜덤한 데이터를 만들어서 처리한 결과이며, 시스템에 따라 다를 수 있으며, Insertion sort와 비교
| 자료 개수 | 처리시간(Insertion sort) | 처리시간(Shell sort) |
| 10000 | 0.000374 | 0.00125 |
| 100000 | 0.003652 | 0.018056 |
| 1000000 | 0.021501 | 0.019016 |
| 100000000 | 2.292645 | 21.730830 |
시간복잡도
최고: n
평균: n^1.5
최악: n^2