5. 삽입정렬에 대해서

 

삽입 정렬(Insertion Sort)

핵심 개념

삽입 정렬은 이미 정렬되니 부분에 새로운 원소를 올바른 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘이다. 

마치 카드 게임에서 손패를 정렬하는 방식과 동일하다. 

 

문제 정의 

- 입력 : 양의 정수 n개의 키를 가진 배열 S[0...n-1]

- 출력 : 오름차순으로 정렬된 배열 S[0...n-1]

- 방법 : 각 원소를 이미 정렬된 부분의 적절한 위치에 삽입

 

핵심 아이디어

1. 첫 번쨰 원소는 이미 정렬이 된 것으로 간주(미정렬부분과 정렬부분은 별개로 분리하여 따로 빼둔다.)

2. 두 번째 원소부터 시작해서 하나씩 처리. 

3. 현재 원소를 정렬된 부분의 올바른 위치에 삽입

4. 모든 원소가 처리될 때까지 반복한다. 

 

단계별 동작 과정

초기 배열: [10, 7, 9, 1, 3, 2, 8, 6, 4, 5]

1단계: i=1, pickData=7

정렬된 부분: [10] | 미정렬 부분: [7, 9, 1, 3, 2, 8, 6, 4, 5]
현재 원소: 7

7을 정렬된 부분에 삽입:
[10] > 7이므로 10을 오른쪽으로 이동
[7, 10] | [9, 1, 3, 2, 8, 6, 4, 5]

2단계: i=2, pickData=9

정렬된 부분: [7, 10] | 미정렬 부분: [9, 1, 3, 2, 8, 6, 4, 5]
현재 원소: 9

9를 정렬된 부분에 삽입:
10 > 9이므로 10을 오른쪽으로 이동
7 < 9이므로 9를 7 다음 위치에 삽입
[7, 9, 10] | [1, 3, 2, 8, 6, 4, 5]

3단계: i=3, pickData=1

정렬된 부분: [7, 9, 10] | 미정렬 부분: [1, 3, 2, 8, 6, 4, 5]
현재 원소: 1

1을 정렬된 부분에 삽입:
10 > 1이므로 10을 오른쪽으로 이동
9 > 1이므로 9를 오른쪽으로 이동
7 > 1이므로 7을 오른쪽으로 이동
1을 맨 앞에 삽입
[1, 7, 9, 10] | [3, 2, 8, 6, 4, 5]

 

이런 식으로 계속 진행하면 최종적으로 정렬이 완료된다.

 

---

기본 구현

#include <iostream>
#include <vector>
using namespace std;

class Sort {
protected:
    vector<int> m_data;
    int m_size;

public:
    Sort() {
        cout << "Sort 생성자 호출" << endl;
    }
    
    // 가상 소멸자로 선언 (중요!)
    virtual ~Sort() {
        cout << "Sort 소멸자 호출" << endl;
        // vector는 자동으로 메모리 해제되므로 특별한 작업 불필요
        // 하지만 로그 출력이나 다른 정리 작업을 할 수 있음
        m_data.clear();  // 명시적으로 벡터 정리 (선택사항)
        m_size = 0;      // 크기 초기화 (선택사항)
    }

    void InitData(vector<int> data) {
        m_data = data;
        m_size = data.size();
    }

    void printall() {
        for (int i = 0; i < m_size; i++) {
            cout << m_data[i] << " ";
        }
        cout << endl;
    }

    virtual void sorting() = 0;
};

class Insertion : public Sort {
public:
    Insertion() {
        cout << "Insertion 생성자 호출" << endl;
    }
    
    // 파생 클래스의 소멸자
    ~Insertion() {
        cout << "Insertion 소멸자 호출" << endl;
        // 파생 클래스에서 추가로 정리할 리소스가 있다면 여기서 처리
    }
    
    void sorting() override;
};

void Insertion::sorting() {
    cout << "삽입 정렬 시작" << endl;
    
    // 두 번째 원소부터 시작 (첫 번째는 이미 정렬된 것으로 간주)
    for (int i = 1; i <= m_size - 1; i++) {
        int pickdata = m_data[i];  // 삽입할 원소
        int cur = i;               // 현재 위치

        // 정렬된 부분에서 삽입 위치 찾기
        while (cur > 0 && m_data[cur - 1] > pickdata) {
            m_data[cur] = m_data[cur - 1];  // 큰 원소를 오른쪽으로 이동
            cur--;                          // 왼쪽으로 이동
        }
        m_data[cur] = pickdata;  // 올바른 위치에 삽입
    }
    
    cout << "삽입 정렬 완료" << endl;
}

int main() {
    cout << "=== 프로그램 시작 ===" << endl;
    
    vector<int> data = {10, 7, 9, 1, 3, 2, 8, 6, 4, 5};
    
    Sort* sortAlg = new Insertion();
    
    sortAlg->InitData(data);
    
    cout << "정렬 전: ";
    sortAlg->printall();
    
    sortAlg->sorting();
    
    cout << "정렬 후: ";
    sortAlg->printall();
    
    cout << "\\n=== 객체 삭제 시작 ===" << endl;
    delete sortAlg;  // 여기서 소멸자들이 호출됨
    
    cout << "=== 프로그램 종료 ===" << endl;
    return 0;
}

 

 

Sort 소멸자에 가상(Virtual)키워드 필수

virtual ~Sort() {  *// virtual 키워드가 중요!// 정리 작업*
}

 

기본 클래스 포인터로 파생 클래스 객체를 삭제할 때 가상 소멸자가 없다면

파생 클래스의 소멸자가 호출 되지 않아서 메모리 누수가 발생할 수 있다.

 

(Windows Visual Studio에서는 이렇지 않았지만 macOS의 Xcode 컴파일러는 꽤나 깐깐한 편.)

 

코드 상세 분석

1. 외부 루프 (원소 선택)

for (int i = 1; i <= m_size - 1; i++)

 

 - i=1부터 시작: 첫 번째 원소(인덱스 0)는 이미 정렬된 것으로 간주

 - i <= m_size - 1: 모든 원소를 처리할 때까지 반복

2. 삽입할 원소 선택

int pickdata = m_data[i];  // 현재 삽입할 원소
int cur = i;               // 삽입 위치를 찾기 위한 인덱스

3. 삽입 위치 찾기 (핵심 로직)

while (cur > 0 && m_data[cur - 1] > pickdata) {
    m_data[cur] = m_data[cur - 1];  // 큰 원소를 오른쪽으로 이동
    cur--;                          // 왼쪽으로 계속 탐색
}

 

 - cur > 0: 배열의 시작을 넘지 않도록 방지

 - m_data[cur - 1] > pickdata: 삽입할 원소보다 큰 원소들을 오른쪽으로 이동

4. 원소 삽입

m_data[cur] = pickdata;  // 찾은 위치에 원소 삽입

의사코드 분석

Insertion Sort (Data):
    for i = 1 to length(Data) - 1:
        pickData = Data[i]
        cur = i
        while cur > 0 and Data[cur-1] > pickData:
            Data[cur] = Data[cur-1]
            cur--
        Data[cur] = pickData

 

---

시간 복잡도 분석

최악의 경우 (Worst Case)

 

- 배열이 역순으로 정렬이 된경우가 최악 케이스. 

 

1번째 패스 : 1번 비교 및 이동

2번쨰 패스 : 2번 비교 및 이동

3번째 패스 : 3번 비교 및 이동.....

(n-1) 패스 : n-1번 비교 및 이동. 

 

총 연산 횟수

T(n) = 1 + 2 + 3 + ... + (n-1)
     = n(n-1)/2
     = O(n²)

 

 

최선의 경우 (Best Case)

배열이 이미 정렬된 경우이다.

 

- 각 패스마다 1번의 비교만 수행(while 조건이 false)

- 이동 연산이 없다. 

- 총 비교 횟수 : n-1번 = O(n)

 

평균의 경우 (Average Case)

시간 복잡도: O(n²)

공간 복잡도

O(1): In-place 정렬로 추가 메모리 거의 사용 안함

 

---

삽입 정렬의 장단점

장점

1. 구현이 간단하고 직관적
2. 적응적 특성: 이미 정렬된 데이터에서 O(n) 성능
3. 안정 정렬: 동일한 값의 상대적 순서 유지
4. In-place 정렬: 추가 메모리 거의 불필요
5. 온라인 알고리즘: 데이터가 하나씩 들어올 때도 처리 가능
6. 작은 데이터셋에서 효율적

단점

1. O(n²) 시간 복잡도: 대용량 데이터에 부적합
2. 역순 정렬된 데이터에서 최악의 성능