셸정렬 시각화
갭 수열을 줄여가며 원거리 요소를 비교 스왑하는 과정을 막대 차트와 아크로 관찰합니다
정렬★★☆
속도
1 / 1현재 갭: 1비교 횟수: 0스왑 횟수: 0
갭 수열
배열 크기20
비교 중스왑갭 그룹정렬 완료
큰 갭부터 시작하여 줄여가며 삽입정렬을 수행하는 과정을 관찰하세요.
큰 갭부터 시작하여 줄여가며 삽입정렬을 수행하는 과정을 관찰하세요.
셸정렬이란?
셸정렬은 Donald Shell이 1959년 발명한 삽입정렬의 개선 알고리즘입니다. 먼 거리 요소를 먼저 비교 교환하여 대략 정렬한 뒤, 갭을 줄여가며 마무리합니다.
사용 방법
- 1배열 크기를 슬라이더로 조절하세요
- 2Shell/Knuth/Hibbard 갭 수열을 선택하세요
- 3랜덤, 거의 정렬, 역순 버튼으로 입력을 생성하세요
- 4재생 버튼으로 정렬 과정을 관찰하세요
- 5보라색 아크가 갭만큼 떨어진 비교를 나타냅니다
동작 원리
- 1큰 갭부터 시작합니다 (예: n/2)
- 2갭만큼 떨어진 요소를 비교하여 교환합니다
- 3각 갭에서 삽입정렬을 수행합니다
- 4갭을 줄이며 반복, 갭=1에서 마무리합니다
- 5시간 복잡도: Shell O(n^2), Knuth O(n^{3/2})
실무 활용
- •임베디드 시스템 — 재귀 없는 제자리 정렬
- •uClibc, bzip2 — 실제 프로젝트에서 사용
- •교육 — 갭 수열 비교로 알고리즘 분석 학습
- •중규모 데이터 — 버블/삽입정렬보다 빠름
비슷한 알고리즘
- •셸정렬 vs 삽입정렬 — 갭 도입으로 원거리 역전을 빠르게 해소
- •셸정렬 vs 퀵정렬 — 퀵정렬은 재귀 필요, 셸정렬은 비재귀
- •빗정렬(Comb Sort) — 버블정렬에 갭 적용한 변형
학습 팁
- •같은 배열에 다른 갭 수열을 적용하여 비교하세요
- •역순 배열에서 큰 갭의 효과를 관찰하세요
- •갭=1 단계에서는 이미 거의 정렬되어 있습니다
- •아크 길이가 갭 크기를 시각적으로 보여줍니다
자주 묻는 질문
Q. 최적 갭 수열은?
A. 아직 미해결 문제입니다. Ciura의 실험적 수열이 실제로 가장 빠릅니다.
Q. 안정 정렬인가요?
A. 아닙니다. 갭만큼 떨어진 교환으로 상대적 순서가 바뀔 수 있습니다.
Q. 시간 복잡도는?
A. 갭 수열에 따라 다릅니다. Shell O(n^2), Hibbard O(n^{3/2}).