정렬 - 삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)

 

오늘은 삽입정렬에 대해 알아보겠습니다. 삽입정렬은 "각 숫자를 적절한 위치에 삽입하는 방식하는 정렬 방법" 입니다.

 

#include <iostream>
#include <vector>

using namespace std;

// 삽입 정렬 함수
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // key보다 큰 원소를 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // key 삽입
    }
}

// 배열 출력 함수
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    
    cout << "정렬 전: ";
    printArray(arr);
    
    insertionSort(arr);
    
    cout << "정렬 후: ";
    printArray(arr);

    return 0;
}

 

삽입정렬은 비교적 느린 정렬 알고리즘에 속하지만, 쉽게 생각할 수 없는 조금 복잡한 구조를 가지고 있습니다. 기본적으로 삽입정렬은 정렬이 되어있다고 가정을 한다는 점에서 특정한 경우에 따라 매우 빠른 속도를 자랑합니다. 소스코드 상에 반복문이 두 번 들어가있어 O(n^2)의 시간복잡도를 가집니다.

 

이제 삽입정렬의 동작과정을 살펴보겠습니다.

 

1. 배열에서 두 번째 요소부터 시작해서, 앞에 정렬된 부분과 비교합니다.

2. 비교한 값이 더 작다면, 그 값을 알맞은 위치에 삽입합니다.

3. 이 과정을 배열의 끝까지 반복합니다.

 

이제 이 과정을 예시로 설명하겠습니다. [5, 3, 8, 4, 2]가 있을 때, 오름차순으로 삽입정렬을 실행하면 처음에 5는 이미 정렬된 상태라고 가정합니다. 두번째 요소 3을 5와 비교하고 3이 더 작기때문에 3을 앞에 삽입합니다. 세번째 요소 8은 이미 정렬된 요소 3, 5와 비교합니다. 8은 이보다 크므로 그대로 유지합니다. 네번째 요소 4를 앞에 3, 5, 8과 비교합니다. 3보다는 크고 5보다는 작기 때문에 3 뒤에 삽입합니다. 마지막 요소 2를 앞에 정렬된 부분과 비교하여 가장 작으므로 맨 앞에 삽입합니다. 이렇게 모든 과정을 마치면 [2, 3, 4, 5, 8]이 만들어집니다.

 

삽입정렬의 특징

시간복잡도 : O(n^2)

=> 최악의 경우(리스트가 역순으로 정렬된 경우) : O(n^2), 최선의 경우(리스트가 이미 정렬된 경우) : O(n), 평균 : O(n^2)

공간복잡도 : O(1)

=> 삽입정렬은 제자리 정렬로 별도의 추가 메모리 공간을 거의 사용하지 않습니다.

안정성 : 안정정렬

=> 같은 값을 가진 요소들의 순서는 정렬 후에도 유지됩니다.

 

장단점

장점

- 간단한 구현

- 작은 데이터에서 효과적

- 안정정렬

- 실시간 데이터 정렬 가능

 

단점

- 큰 데이터에서 비효율적

- 비교적 느린 성능

 

삽입정렬의 활용

삽입정렬의 장점을 보면 작은 데이터와 실시간 데이터 정렬에 유용합니다. 고로 거의 정렬된 데이터이거나, 작은 데이터셋에서의 정렬, 실시간 정렬에 사용됩니다. 그리고 삽입정렬은 하이브리드 알고리즘으로 병합 정렬, 퀵 정렬과 같은 고급 알고리즘과 결합되어 사용할 수 있습니다. 예를 들어, 배열의 크기가 일정 이하로 작아지면 삽입정렬로 전환하여 처리하는 하이브리드 방식은 효율성을 극대화할 수 있습니다.

 

NEXT

오늘은 삽입정렬에 대해 알아보았습니다. 전체적으로 이전에 알아본 버블정렬과 비슷한 느낌이지만, 버블정렬은 불필요한 비교와 교환연산이 많아 전체적인 성능이 더 떨어지기 때문에 삽입정렬이 일반적으로 버블정렬보다 빠릅니다. 다음에는 드디어 매우 중요한 퀵정렬에 대해 살펴보도록 하겠습니다. 감사합니다.