Shell Sort(셸 정렬)는 삽입 정렬(Insertion Sort)을 확장한 정렬 알고리즘으로, 배열을 한 번에 정렬하지 않고 일정 간격(gap)으로 떨어진 원소들끼리 먼저 정돈한 뒤, gap을 점진적으로 줄여가며 정렬을 완성하는 방식입니다.
Insertion Sort가 “인접한 원소(거리 1)를 기준으로 삽입”한다면, Shell Sort는 “멀리 떨어진 원소를 먼저 이동시켜 전체 구조를 빠르게 정돈”합니다.
즉, Shell Sort는 초기 단계에서 큰 이동을 허용하여 데이터의 뒤섞임을 빠르게 완화하고, 마지막 단계에서 Insertion Sort로 미세 정렬을 수행하는 구조입니다.
1. Shell Sort의 구조와 동작 방식
1.1 기본 아이디어
Shell Sort의 핵심 아이디어는 단순합니다.
- 배열을 gap 간격으로 떨어진 원소들끼리 묶은 부분 배열처럼 취급한다
- 각 부분 배열을 Insertion Sort(shift) 방식으로 정렬한다
- gap을 줄여가며 이 과정을 반복한다
gap이 줄어들수록 배열은 점점 “거의 정렬된 상태”가 되며, 마지막 gap = 1 단계에서는 사실상 Insertion Sort의 최적 상황이 됩니다.
1.2 gap의 의미
Shell Sort에서 gap은 비교 및 이동이 이루어지는 거리 단위를 의미합니다. Insertion Sort가 인접 원소(거리 1)를 기준으로 비교·이동한다면, Shell Sort는 gap만큼 떨어진 원소들을 기준으로 비교·이동합니다.
일반적인 구현에서는 gap을 다음처럼 줄여갑니다.
gap = n / 2
gap = n / 4
...
gap = 1
Shell Sort의 성능은 gap 수열 선택에 따라 크게 달라질 수 있습니다. 절반 감소 방식 외에도 Knuth 수열, Hibbard 수열 등 다양한 전략이 제안되어 있으며, 일부 수열은 평균 성능을 더 개선할 수 있습니다. 다만 이 문서에서는 알고리즘 구조 이해와 구현 단순성을 우선하여, 가장 직관적인 절반 감소 방식을 사용합니다.
또한 gap은 “그룹의 개수”로도 해석할 수 있습니다.
gap = g일 때, 배열은 논리적으로 g개의 그룹(부분 배열)로 나뉘며, 각 그룹은 index % g가 같은 원소들로 구성됩니다.
- 그룹 0: index % g == 0
- 그룹 1: index % g == 1
- ...
- 그룹 g-1: index % g == g-1
즉, gap 값은 동시에 수행되는 부분 Insertion Sort의 개수라고 볼 수 있습니다. gap이 클수록 그룹은 많고(조각이 많음), 각 그룹 길이는 짧아집니다. gap이 줄어들수록 그룹은 줄고, 각 그룹 길이는 길어지며, 마지막 gap = 1에서는 배열 전체가 하나의 그룹이 되어 일반적인 Insertion Sort가 됩니다.
1.2.1 예제로 살펴보기
예를 들어, 다음과 같은 배열이 있다고 해 보겠습니다.
예제 배열: [64, 25, 12, 22, 11]
이 배열에서 gap = 2를 적용하면, 인덱스를 2로 나눈 나머지 기준으로 배열은 논리적으로 2개의 그룹으로 나뉩니다.
- 그룹 0: index
0, 2, 4→ 값[64, 12, 11] - 그룹 1: index
1, 3→ 값[25, 22]
Shell Sort는 이 그룹들을 실제로 분리된 배열로 만들지는 않지만, 각 그룹을 하나의 부분 배열처럼 취급하여 각각 Insertion Sort 방식으로 정렬합니다.
이처럼 gap은 비교·이동 거리이면서 동시에 배열을 어떻게 묶어서 바라볼 것인가를 결정하는 기준이 됩니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Shell Sort의 간격(gap)을 두고 떨어진 원소들을 먼저 부분 정렬한 뒤, gap을 점점 줄여가며 전체 배열을 정렬하는 과정을 단계별로 시각화해 주는 도구입니다. Insertion Sort가 인접한 이동에 집중한다면, Shell Sort는 먼 거리 이동을 먼저 허용해 전체 이동 비용을 줄이는 전략이 어떻게 동작하는지 직관적으로 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. Pass 단위 동작 (gap 기반)
Shell Sort는 “Pass i” 대신 gap 단위 Pass로 이해하는 것이 자연스럽습니다.
- 하나의 gap 값이 하나의 큰 Pass
- 해당 gap 동안 여러 개의 부분 Insertion Sort(shift 기반)가 수행됨
gap = g일 때의 동작 구조
i = g부터 시작- 같은 그룹 내에서
i, i-g, i-2g ...를 비교 - 큰 값을 gap 단위로 오른쪽으로 밀고(shift), 빈 자리에 key 삽입
즉, Insertion Sort의 “한 칸 이동”을 Shell Sort는 “gap 칸 이동”으로 확장한 형태입니다.
3. 왜 Insertion Sort보다 빠른가?
Insertion Sort의 약점은 멀리 잘못 배치된 값이 한 칸씩만 이동한다는 점입니다. 이 때문에 입력이 뒤섞여 있으면 이동(shift) 비용이 크게 증가합니다.
Shell Sort는 이를 보완하기 위해 초기 단계에서 gap 간격 이동을 허용합니다. 즉, 큰 gap 단계에서 값들이 제자리 “근처”로 빠르게 이동하고, 마지막 gap = 1 단계에서는 배열이 이미 거의 정렬된 상태이므로 Insertion Sort가 매우 적은 이동만으로 마무리됩니다.
3.1 간단한 예제로 비교해 보기
예를 들어, 다음과 같은 배열을 생각해 보겠습니다.
예제 배열: [64, 25, 12, 22, 11]
이 배열에서 가장 작은 값 11은 맨 뒤(index 4)에 위치해 있으며, 정렬이 끝나면 맨 앞(index 0)으로 이동해야 합니다.
√ Insertion Sort의 경우
- 11은 인접 원소와만 비교·이동할 수 있으므로
index 4 → 3 → 2 → 1 → 0순서로- 한 칸씩 총 4번 이동해야 합니다
이처럼 Insertion Sort에서는 멀리 잘못 배치된 값일수록 이동 비용이 크게 증가합니다.
√ Shell Sort의 경우
Shell Sort는 초기 단계에서 gap 간격 이동을 허용하여, 이와 같은 부담을 미리 줄입니다.
gap = 2 단계에서 11은 같은 그룹(index 0, 2, 4)에 속하며, 다음과 같은 순서로 이동합니다.
초기 상태
[64, 25, 12, 22, 11]
12 > 11 이므로, 12를 index 4로 이동
[64, 25, 12, 22, 12]
이어서 64 > 11 이므로, 64를 index 2로 이동
[64, 25, 64, 22, 12]
마지막으로 key(11)를 index 0에 삽입
[11, 25, 64, 22, 12]
(참고) 위 변화는 gap=2 단계 중에서도 i=4(key=11)를 처리하는 과정만 떼어 보여준 것입니다. gap=2 단계가 모두 끝나면 배열은 큰 값은 뒤로, 작은 값은 앞으로 어느 정도 재배치됩니다.
이 시점에서 배열은 완전히 정렬된 것은 아니지만, 가장 작은 값이 이미 맨 앞으로 이동하여 이후 단계에서 필요한 이동(shift) 부담이 크게 줄어듭니다.
이후 gap = 1 단계에서는 배열이 이미 거의 정렬된 상태이므로, Insertion Sort는 최소한의 이동만으로 정렬을 마무리합니다.
최종 결과: [11, 12, 22, 25, 64]
즉, Shell Sort는 멀리 잘못 배치된 값을 초기에 크게 이동시켜, Insertion Sort가 부담스러워하는 상황을 미리 제거한 뒤 정렬을 완성합니다.
4. 시간 복잡도는 왜 애매한가?
Shell Sort는 gap 수열에 따라 성능이 크게 달라지는 알고리즘입니다.
- 최악의 경우: O(N²)
- 일반적인 경우: O(N1.3 ~ N1.5)
- 최선의 경우: O(N log N)에 근접
시간 복잡도가 명확히 하나로 떨어지지 않는 이유는, gap 선택 전략이 알고리즘 성능에 결정적인 영향을 주기 때문입니다. 하지만 구현이 매우 단순한데도 체감 성능이 좋아, 실용적으로 자주 언급되는 정렬입니다.
5. 실행 흐름을 예제로 이해하기
예제 배열: [64, 25, 12, 22, 11]
정렬 기준: 오름차순
아래 예제에서는 절반 감소 gap 수열을 사용합니다.
n = 5
gap = n/2 = 2
gap = 1
5.1 gap = 2 단계
gap이 2라는 것은, 인덱스 차이가 2인 원소들끼리 같은 그룹(부분 배열)로 묶어서 정렬한다는 뜻입니다.
즉, 배열은 다음 2개의 그룹으로 나뉩니다.
- 그룹 0: index
0, 2, 4→ 값[64, 12, 11] - 그룹 1: index
1, 3→ 값[25, 22]
Shell Sort는 이 그룹들을 각각 Insertion Sort(shift) 방식으로 정렬합니다. (단, 이동 간격은 1이 아니라 gap=2 입니다)
그럼 이 두 그룹은 코드에서 어떻게 처리될까요?
Shell Sort에서는 그룹마다 별도의 루프를 두지 않습니다. 대신, 아래 i 루프 하나가 여러 그룹을 번갈아 오가며 처리를 수행합니다.
for (int i = gap; i < n; i++)
gap = 2인 경우, 그룹은 index % 2 값으로 결정됩니다. 따라서 i가 증가함에 따라, 처리 대상 그룹도 자연스럽게 바뀝니다.
i = 2→ 그룹 0 (index 2)i = 3→ 그룹 1 (index 3)i = 4→ 그룹 0 (index 4)
즉, Shell Sort는 그룹 0을 끝까지 정렬한 뒤 그룹 1로 넘어가는 방식이 아니라, i가 증가하는 흐름 안에서 그룹을 오가며 각 그룹에 대해 동일한 로직(삽입 정렬)을 번갈아 적용합니다.
이 구조 덕분에 코드가 단순해지며, 하나의 gap 단계 안에서 여러 부분 배열이 동시에 정렬됩니다.
1) i = 2 (key = 12) : 그룹 0 내부 삽입
- key = 12
- j = 2
- 비교 대상:
array[j - 2] = array[0] = 64
64 > 12이므로 64를 index 2로 shift하고, key(12)를 index 0에 삽입합니다.
결과 배열: [12, 25, 64, 22, 11]
2) i = 3 (key = 22) : 그룹 1 내부 삽입
- key = 22
- j = 3
- 비교 대상:
array[j - 2] = array[1] = 25
25 > 22이므로 25를 index 3으로 shift하고, key(22)를 index 1에 삽입합니다.
결과 배열: [12, 22, 64, 25, 11]
3) i = 4 (key = 11) : 그룹 0 내부 삽입
- key = 11
- j = 4
- 비교 대상:
array[j - 2] = array[2] = 64
64 > 11이므로 64를 index 4로 shift합니다. 이어서 j가 2가 되고, 다시 array[0] = 12와 비교하여 12 > 11이므로 12도 index 2로 shift합니다. 마지막으로 key(11)를 index 0에 삽입합니다.
gap=2 단계 최종 결과: [11, 22, 12, 25, 64]
이 시점에서 배열이 완전히 정렬된 것은 아니지만, 큰 값(64)이 뒤쪽으로 빠르게 이동했고, 작은 값(11)도 앞으로 당겨져 전체 구조가 크게 정돈된 상태가 됩니다.
5.2 gap = 1 단계 (마지막 정리: Insertion Sort)
gap이 1이 되면 Shell Sort는 사실상 일반 Insertion Sort와 완전히 동일해집니다. 하지만 앞 단계에서 이미 배열이 상당히 정돈되어 있기 때문에, 이 Insertion Sort는 매우 적은 이동만으로 빠르게 끝납니다.
현재 배열: [11, 22, 12, 25, 64]
- i = 1 (key=22): 이동 없음
- i = 2 (key=12): 22만 한 칸 shift 후 12 삽입 →
[11, 12, 22, 25, 64] - i = 3 (key=25): 이동 없음
- i = 4 (key=64): 이동 없음
최종 결과: [11, 12, 22, 25, 64]
6. C# 기반 Shell Sort 구현
using System;
namespace Daebak.Common.Algorithms.Sorting
{
public static class ShellSort
{
public static void Sort(int[] array)
{
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
int n = array.Length;
if (n <= 1)
{
return;
}
// gap을 절반씩 줄여가며 반복
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i++)
{
int key = array[i];
int j = i;
while (j >= gap && array[j - gap] > key)
{
array[j] = array[j - gap];
j -= gap;
}
array[j] = key;
}
}
}
}
}
이 구현은 gap 기반 Insertion Sort의 전형적인 형태이며, Insertion Sort와 동일한 shift 구조를 gap 간격으로 확장한 것입니다.
7. Unity 환경에서 테스트 해보기
using UnityEngine;
using Daebak.Common.Algorithms.Sorting;
public class Test_ShellSort : MonoBehaviour
{
private void Start()
{
int[] data = new int[] { 64, 25, 12, 22, 11 };
Debug.Log("Before Sort : " + string.Join(", ", data));
ShellSort.Sort(data);
Debug.Log("After Sort : " + string.Join(", ", data));
}
}
출력 결과
Before Sort : 64, 25, 12, 22, 11
After Sort : 11, 12, 22, 25, 648. Shell Sort의 특징과 한계
1) Insertion Sort의 상위 호환(체감 성능 개선)
- Shell Sort는 멀리 떨어진 원소를 먼저 이동시켜 배열을 빠르게 정돈하고, 마지막에 Insertion Sort로 마무리합니다. 특히 입력이 뒤섞인 상태일수록 Insertion Sort보다 유리한 경우가 많습니다.
2) 안정 정렬(Stable Sort)이 아님
- gap 이동 과정에서 같은 키의 상대 순서가 바뀔 수 있으므로, Shell Sort는 안정 정렬이 아닙니다.
3) 구현은 단순하지만, 성능은 gap 수열에 민감
- 코드는 단순하지만 gap 수열에 따라 성능 편차가 큽니다. 이 문서에서는 설명을 단순화하기 위해 절반 감소 수열을 사용했습니다.
9. 마무리
Shell Sort는 “먼 거리 이동으로 전체 구조를 먼저 정돈한 뒤, 삽입 정렬로 마무리”하는 정렬입니다.
- gap을 줄여가며 여러 부분 Insertion Sort를 수행
- 초기 큰 이동으로 뒤섞임을 빠르게 완화
- 마지막 gap=1 단계에서 Insertion Sort로 정렬 완성
Insertion Sort를 이해한 상태에서 Shell Sort를 보면, “이동 비용(shift)을 줄이기 위한 전략”이 훨씬 선명하게 보입니다. 이 관점을 가지고 이후 Merge Sort, Quick Sort를 보면 정렬 비용 구조를 더 쉽게 비교할 수 있습니다.
※ 다음 글에서는 Merge Sort를 살펴보며, 데이터를 직접 이동시키며 정렬하는 방식에서 벗어나 배열을 분할한 뒤 정렬된 결과를 병합하는 구조 중심의 정렬 방식을 정리합니다.
'자료 구조' 카테고리의 다른 글
| 대박 게임 개발 연구소(Daebak Game Dev Lab) 소개 (0) | 2026.01.15 |
|---|---|
| Unity 개발자를 위한 C# Merge Sort(병합 정렬) 구현 (0) | 2026.01.15 |
| Unity 개발자를 위한 C# Insertion Sort(삽입 정렬) 구현 (0) | 2026.01.14 |
| Unity 개발자를 위한 C# Selection Sort(선택 정렬) 구현 (0) | 2026.01.14 |
| Unity 개발자를 위한 C# Bubble Sort(버블 정렬) 구현 (0) | 2026.01.14 |
