[C++ - TIL] 삽입 정렬의 진화, 쉘 정렬(Shell Sort)의 원리와 효율성

🎮 주제 : 삽입 정렬의 진화, 쉘 정렬(Shell Sort)의 원리와 효율성

태그 : #C++ #알고리즘 #삽입정렬 #쉘정렬 #정렬최적화 #시간복잡도

---

📌 학습 요약

• 삽입 정렬의 재발견 : 배열이 이미 정렬된 최선의 경우(Best-case) **O(n)**의 속도를 내는 삽입 정렬의 특성을 파악하고, 이를 활용해 전체 효율을 높이는 전략 이해
• 쉘 정렬(Shell Sort)의 핵심 : 멀리 떨어진 요소들을 먼저 비교하여 대략적으로 정렬(Gap Sort)한 뒤, 간격(gap)을 점차 줄여가며 최종적으로 삽입 정렬을 수행해 이동 횟수를 획기적으로 줄임
• 연산 최적화 (Shift vs Swap) : 매번 세 번의 대입이 일어나는 swap 대신, 큰 값을 한 칸씩 뒤로 미는 이동(Shift) 후 적절한 위치에 **대입(Insert)**하는 방식이 더 효율적임을 학습
• 통합적 루프 설계 : gap이 1이 되는 순간이 곧 일반적인 삽입 정렬임을 이해하고, 별도의 예외 처리 없이 하나의 반복문 안에서 모든 정렬 단계가 완료되도록 구현

---

🛠 주요 코드 및 구현 상세

1. 쉘 정렬(Shell Sort) 구현 (이동+대입 방식)

int gap = size / 2;  // 1. 초기 간격(Gap) 설정

// 간격이 1이 될 때까지 반복 (마지막 단계는 일반 삽입 정렬과 동일)
while (gap >= 1) {
    for (int i = gap; i < size; i++) {
        int temp = list[i]; // 삽입할 값 보관
        int j = i;

        // 2. while문을 통한 적절한 위치 탐색 및 이동(Shift)
        // [조건] j가 gap보다 크고, 앞쪽 원소(list[j-gap])가 temp보다 크면
        while (j >= gap && list[j - gap] > temp) {
            list[j] = list[j - gap];  // 큰 값을 뒤로 밀기
            j -= gap;                 // gap만큼 앞으로 이동하며 계속 비교
        }
        
        // 3. 최종적으로 찾아낸 빈 공간에 값 삽입
        list[j] = temp;
    }
    gap /= 2;  // 4. 간격을 줄여가며 정렬의 정밀도 높임
}

---

✅ 주요 문법 및 개념 정리

개념 특징 성능 향상 포인트

삽입 정렬	거의 정렬된 배열에서 최강의 성능	**O(n^2)**의 최악 사례를 쉘 정렬로 보완
Gap (간격)	그룹을 나누는 기준	멀리 떨어진 요소를 빠르게 제자리 근처로 보냄
Shift (이동)	list[j] = list[j - gap]	swap보다 대입 연산 횟수를 1/3로 절약
Best-case	데이터가 이미 정렬된 상태	삽입 정렬 기준 O(n) 달성 가능

💡 알고리즘 인사이트 : 왜 쉘 정렬인가?

• 삽입 정렬은 '한 칸씩'만 이동하기 때문에, 아주 작은 값이 배열 맨 끝에 있다면 맨 앞까지 오기 위해 수많은 교환이 필요함
• 쉘 정렬은 '성긴 간격'으로 큼직하게 먼저 이동시켜 놓기 때문에, 마지막 삽입 정렬 단계에서 원소들이 이동해야 할 거리가 매우 짧아져 전체 속도가 빨라짐

---

✨ 느낀 점

• 삽입 정렬의 O(n) 특성이 쉘 정렬이라는 더 큰 알고리즘의 발판이 된다는 점이 논리적으로 매우 흥미로웠음
• 단순한 swap보다 이동 후 대입하는 방식이 미세하지만 확실한 성능 차이를 만든다는 것을 보며 '디테일한 최적화'의 중요성을 깨달음
• gap이 1일 때의 특수 상황을 별도 코드로 분리하지 않고 루프 안에 녹여내는 설계 방식에서 코드의 간결함과 효율성을 동시에 배움
• 조건식 하나(list[j - gap] > temp)가 정렬의 방향과 기준을 결정짓는 핵심 키라는 것을 다시 한번 체감함