셸 정렬 (Shell Sort)

셸 정렬 (Shell Sort)

삽입 정렬을 개선한 정렬 알고리즘으로, 일정 간격(gap)으로 떨어진 원소들을 먼저 정렬한 후 간격을 줄여가며 최종적으로 삽입 정렬을 수행하는 방식

목적: 삽입 정렬의 비효율성 개선, 중간 복잡도 정렬, 제자리 정렬

특징: 간격 기반 부분 정렬, 불안정 정렬, 제자리 정렬, 간격 시퀀스 의존

동작 원리

간격 시퀀스(Gap Sequence)

• •Shell 원래: n/2, n/4, ..., 1 → O(n²) 최악
• •Hibbard: 1, 3, 7, 15, ... (2^k - 1) → O(n^1.5)
• •Knuth: 1, 4, 13, 40, ... ((3^k - 1)/2) → O(n^1.5)
• •Sedgewick: 1, 5, 19, 41, 109, ... → O(n^(4/3)) 추정

시간 복잡도

• •최선: O(n log n) (거의 정렬된 경우)
• •평균: O(n^1.25) ~ O(n^1.5) (간격 시퀀스 의존)
• •최악: O(n²) (원래 간격) 또는 O(n^1.5) (개선된 간격)

공간 복잡도: O(1) - 제자리 정렬

장점: 삽입 정렬보다 빠름, 제자리 정렬, 구현 간단, 작은 배열에 효율

단점: 불안정 정렬, 최적 간격 시퀀스 미확정, 최악 O(n²) 가능

적용사례: 중간 크기 배열, 임베디드 시스템, 교육용

비교: 셸(O(n^1.5)/제자리) vs 삽입(O(n²)/안정) vs 퀵(O(n log n)/불안정)

연관: 삽입 정렬, 정렬 알고리즘, 간격 시퀀스, 제자리 정렬