정의
셸 정렬(Shell sort)은 비교 기반 정렬 알고리즘 중 하나로, 삽입 정렬을 확장한 형태이다. 배열의 원소들을 일정 간격(gap)으로 나누어 부분 배열을 삽입 정렬 방식으로 정렬한 뒤, 간격을 점차 줄여가며 전체 배열을 정렬한다. 1959년 미국의 컴퓨터 과학자 도널드 셸(Donald Shell)이 처음 제안하였다.
알고리즘 개요
- 초기 간격 선택: 배열 길이 n에 대해 초기 간격 gap을 설정한다. 일반적인 선택으로는 gap = n/2가 사용된다.
- 간격에 따른 정렬: 현재 gap에 대해, 인덱스 i = gap 부터 n – 1까지 순회하면서, 원소 *A[i]*를 앞쪽에 있는 gap 간격의 원소들과 비교·교환한다. 이는 삽입 정렬을 gap 간격으로 적용한 것과 동일하다.
- 간격 감소: gap을 감소시킨다. 일반적인 감소 방법은 gap = gap / 2 (정수 나눗셈)이며, 헌리(Hibbard), 셈(Sedgewick) 등 다양한 간격 수열이 제시되어 있다.
- 반복: gap 값이 0이 될 때까지 2~3 단계를 반복한다. 최종적으로 gap이 1일 때 수행되는 삽입 정렬이 전체 배열을 완전 정렬한다.
시간 복잡도
| 간격 수열 | 최악 시간 복잡도 | 평균 시간 복잡도 | 비고 |
|---|---|---|---|
| 단순 반으로 감소 (Shell’s original) | O(n²) | O(n²) | 초기 제안 |
| 헌리 수열 (gap = 2^k – 1) | O(n^(3/2)) | — | 개선된 성능 |
| 셈 수열 (예: 1, 5, 19, 41, …) | O(n^(4/3)) | — | 실용적 사용 |
| 프리톤 수열 (Pratt) | O(n log² n) | — | 이론적 최적화 |
가장 일반적으로 사용되는 간격 수열(반으로 감소)에서는 최악·평균 복잡도가 O(n²)이며, 간격 수열을 적절히 선택하면 n log n에 가까운 성능을 얻을 수 있다.
공간 복잡도
정렬 수행 과정에서 추가 메모리를 거의 사용하지 않으므로, 최악·평균·최소 모두 O(1)인 제자리(in‑place) 정렬이다.
안정성
삽입 정렬을 기반으로 하므로, 같은 값의 원소 간 상대 순서는 간격이 1이 되는 단계에서 교환될 수 있다. 따라서 셸 정렬은 비안정 정렬에 해당한다.
특징 및 활용
- 중간 규모 데이터에 대해 퀵 정렬이나 병합 정렬보다 구현이 간단하고, 메모리 사용이 적어 실시간 시스템이나 임베디드 환경에서 사용된다.
- 부분 정렬된 데이터에 대해 빠르게 정렬을 완성할 수 있다. 초기 간격 단계에서 이미 대부분 정렬된 상태라면 전체 연산량이 크게 감소한다.
- 현대 표준 라이브러리에서는 일반적인 정렬 알고리즘으로 채택되지 않지만, 교육용 예시와 특정 상황(예: 제한된 메모리·코드 크기)에서 활용된다.
역사
1959년 도널드 셸은 “Sorting by gaps”라는 논문에서 현재의 셸 정렬 아이디어를 제시하였다. 이후 다양한 간격 수열이 연구되었으며, 1970년대와 1980년대에 제안된 헌리·셈·프리톤 수열 등이 알고리즘의 효율성을 크게 향상시켰다.
관련 알고리즘
- 삽입 정렬 (Insertion sort) – 셸 정렬의 기본 정렬 방식.
- 퀵 정렬 (Quick sort), 병합 정렬 (Merge sort) – 평균·최악 시간 복잡도 측면에서 셸 정렬과 비교되는 대표적인 정렬 알고리즘.
- 비트 전송 정렬 (Bitonic sort), 힙 정렬 (Heap sort) – 다른 제자리 정렬 방식과 함께 학습 대상이 된다.
참고 문헌
- D. L. Shell, “Sorting by gaps,” Communications of the ACM, vol. 2, no. 5, pp. 58‑59, 1959.
- H. S. Sedgewick, “Algorithms in C, Parts 1‑4: Fundamentals, Data Structures, Sorting, Searching,” Addison‑Wesley, 1998.
위 내용은 공인된 알고리즘 교과서와 학술 논문에 기반한 객관적인 서술이다.
