1. 쉘 정렬(Shell Sort)이란?
쉘 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 발전시킨 정렬 알고리즘으로, 먼 거리의 요소들을 먼저 정렬하여 배열을 부분적으로 정렬한 후, 점진적으로 더 작은 간격을 사용하여 정렬을 수행합니다. 이를 통해 삽입 정렬의 단점을 보완하며, 좀 더 효율적인 정렬을 가능하게 합니다.
(삽입 정렬에 대해 잘 모르시다면 삽입 정렬에 대한 글을 읽과 와주세요! )
2. 동작 방식
쉘 정렬의 동작 방식은 다음과 같습니다
- 정렬할 배열을 일정한 간격(Gap)으로 나눕니다. 이 간격은 처음에는 배열의 크기를 반으로 나눈 값이나, 일반적으로는 이전 간격을 절반으로 나눈 값으로 시작합니다.
- 각 부분 배열에 대해 삽입 정렬을 수행합니다. 이때, 간격만큼 떨어진 요소들을 서로 비교하며 정렬합니다.
- 간격을 점점 줄여가며 정렬을 반복합니다. 간격이 1이 될 때까지 반복합니다.
즉, 쉘 정렬은 삽입 정렬의 단점인 작은 값들이 배열의 끝으로 이동하는 것을 개선하기 위해 멀리 떨어져 있는 요소들끼리 비교하여 먼저 정렬하고, 이후에 간격을 줄여가며 최종적으로 전체 배열을 정렬하는 방법입니다.
3. 코드
#include <stdio.h>
void ShellSort(int a[], int n) {
int i, j, key, t;
for (t = n / 2; t >= 1; t /= 2) {
for (i = t; i < n; i++) {
key = a[i];
for (j = i - t; j >= 0; j-=t) {
if (key >= a[j]) break;
a[j + t] = a[j];
}
a[j + t] = key;
}
}
}
int main(void) {
int a[] = { 18, 26, 14, 7, 9, 36, 25, 17, 30, 29 };
int i, n = sizeof(a) / sizeof(int);
printf("정렬 전 : ");
for (i = 0; i < n; i++) printf(" % d ", a[i]);
ShellSort(a, n);
printf("\n삽입 정렬 후 : ");
for (i = 0; i < n; i++) printf(" % d ", a[i]);
return 0;
}주어진 코드는 C 언어로 구현된 쉘 정렬(Shell Sort) 알고리즘입니다. 이 코드는 주어진 배열을 오름차순으로 정렬하는 함수 ShellSort와 메인 함수 main으로 구성되어 있습니다.
함수 ShellSort는 쉘 정렬 알고리즘을 구현한 것으로, 입력으로 주어진 배열 a를 오름차순으로 정렬합니다. 쉘 정렬은 삽입 정렬의 단점을 보완한 정렬 알고리즘이며, 일정한 간격(t)으로 배열을 나누어 삽입 정렬을 수행합니다.
메인 함수 main은 주어진 배열 a를 출력하고, 쉘 정렬 알고리즘을 이용하여 정렬 후 배열을 다시 출력하는 역할을 합니다.
이 코드의 동작은 다음과 같습니다
- 주어진 배열
a를 출력합니다. (정렬 전)- 함수
ShellSort를 호출하여 배열a를 오름차순으로 정렬합니다.- 정렬된 배열
a를 출력합니다. (쉘 정렬 후)
예를 들어, 주어진 배열 a가 {18, 26, 14, 7, 9, 36, 25, 17, 30, 29}인 경우, 출력은 다음과 같을 것입니다:
정렬 전: 18 26 14 7 9 36 25 17 30 29
쉘 정렬 후: 7 9 14 17 18 25 26 29 30 36정렬이 잘 이루어진 것을 확인할 수 있습니다. 위 코드는 쉘 정렬 알고리즘을 제대로 구현하고 있으며, C 언어로 배열을 정렬하는 데 사용될 수 있습니다.
4. 시간 복잡도
쉘 정렬은 삽입 정렬(Insertion Sort)을 개선한 알고리즘이며, 간격(t)별로 삽입 정렬을 수행하여 배열을 점차 정렬하는 방식으로 동작합니다. 간격은 일반적으로 이전 간격을 절반으로 나눈 값으로 시작하며, 최종적으로 간격이 1이 될 때까지 정렬합니다.
이 글에서 언급한 삽입 정렬을 내포하고 있는 것은 쉘 정렬이기 때문에 쉘 정렬의 산술적인 시간 복잡도는 O(log2n n^2)로 나타내지만, 실제로는 O(n log2n)에 매우 가까운 결과를 얻을 수 있습니다. 이러한 이유는 간격에 따라 삽입 정렬을 수행하며, 정렬되어 있는 데이터에 대해서는 삽입 정렬의 효율성을 누릴 수 있기 때문입니다.
따라서 쉘 정렬의 평균적인 시간 복잡도는 O(n log2n)으로, 일반적인 O(n^2) 정렬 알고리즘보다 훨씬 빠른 속도로 정렬을 수행할 수 있습니다. "<<<" 기호는 왼쪽 값보다 오른쪽 값이 비교가 안될 정도로 크다는 의미로, 쉘 정렬의 시간 복잡도가 O(n log2n)이 O(n^2)보다 매우 작음을 나타냅니다.
