삽입정렬, 왜 느려질까?
삽입정렬은 "거의 정렬된 배열"에는 정말 빠릅니다. 그런데 한 가지 약점이 있어요. 작은 값이 배열의 맨 뒤에 있으면, 그 값이 제자리(맨 앞)까지 가는 데 한 칸씩 밀려가야 합니다. 9칸 떨어져 있으면 9번, 100칸이면 100번. 멀리 있는 값일수록 손해가 커집니다.
예:
[8, 5, 3, 9, 2, 7, 4, 1, 6]에서1은 거의 끝(인덱스 7)에 있습니다. 삽입정렬이라면1이 맨 앞으로 가기 위해 옆 원소를 일곱 번이나 밀어내야 해요.
이 "한 칸씩만 이동" 때문에 삽입정렬은 무작위 배열에서 O(n²)까지 느려집니다.
핵심 아이디어 — "간격(gap)"을 두고 본다
셸 정렬(Shell Sort)의 발상은 단순합니다. 처음부터 옆 칸끼리 보지 말고, 멀리 떨어진 원소끼리 먼저 정리하자.
- •먼저 gap칸 떨어진 원소끼리만 묶어서 삽입정렬합니다. (예: gap=4 면 인덱스 0·4·8 끼리, 1·5 끼리…)
- •그 다음 gap을 절반으로 줄여 더 촘촘하게 봅니다. (4 → 2 → 1)
- •마지막
gap = 1패스는 사실 그냥 삽입정렬입니다. 하지만 이때쯤이면 배열이 이미 거의 정렬돼 있어 이동이 거의 없어요.
흔히 쓰는 간격 수열은 배열 크기 n의 절반에서 시작해 절반씩 줄이는 방식입니다: n/2 → n/4 → … → 1.
왜 gap을 쓰면 빨라질까?
비결은 "큰 점프" 에 있습니다.
gap이 클 때는, 멀리 뒤에 있던 작은 값이 한 번의 교환으로 큰 거리를 점프합니다. 위 예시에서 1은 gap이 큰 패스에서 단번에 앞쪽으로 크게 이동하죠. 한 칸씩 가는 삽입정렬과는 전혀 다릅니다.
그래서 gap을 점점 줄여 마지막 gap = 1에 도달했을 때는, 남아 있는 이동량이 확 줄어 있습니다. 큰 gap들이 "큰 그림"을 먼저 맞춰두고, 작은 gap이 "마무리"만 하는 셈이에요.
정리하면 이런 흐름입니다.
1. gap = n/2 로 시작한다
2. gap칸 떨어진 그룹들을 각각 삽입정렬한다
3. gap을 절반으로 줄여 2번을 반복한다
4. gap = 1 패스까지 끝나면 정렬 완료
직접 눈으로 확인하기
gap이 4 → 2 → 1로 줄어드는 동안, 멀리 떨어진 막대끼리 비교(노랑)·교환(빨강)되고, 작은 값이 큰 점프로 앞쪽에 자리 잡는 전 과정을 단계별 시각화로 준비했습니다. 각 단계의 gap 값과 변수 변화까지 한눈에 보입니다.
"gap을 두고 멀리부터 정리한다"는 발상은 글로만 보면 추상적이지만, 막대가 큰 점프로 움직이는 걸 한 번 보면 "아, 그래서 빨라지는구나"가 단번에 이해됩니다.