[Algorithm/C++] 삽입 정렬(Insertion Sort) - 비교 후 삽입

 

 

1. 설명

삽입 정렬(Insertion Sort)란 리스트의 값들을 순차적으로 인접한 원소와 비교를 하여 위치를 교환해주며 정렬을 하는 방법 중 하나이다.

 

 

한 원소를 선택하여 위치를 변경해준다는 점에서 선택 정렬(Selection Sort)과 유사하다고 할 수도 있으며 인접한 원소 간 비교를 통하여 위치를 교환해주므로 거품 정렬(Bubble Sort)과도 유사하다고 할 수도 있다.

 

동작 예시 (출처: https://visualgo.net/en/sorting)

 

동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다.

 

 

시작은 두 번째 Index부터 시작하며 왼쪽에 있는 원소들과 비교를 통하여 더 큰 값이 왼쪽에 위치하고 있다면 교환하는 작업을 수행한다.

 

 

이 작업을 반복하여 수행함으로써 가장 작은 원소는 가장 왼쪽의 위치하게 되며, 왼쪽의 있는 원소들은 정렬된 상태가 되는 것이다.

 

 

 

특징

▶ 시간 복잡도는 O(N^2)이다. 평균적으로는 선택 정렬(Selection Sort)과 동일하게 N^2 / 2로서 거품 정렬(Bubble Sort)과 효율성은 동일해도 2배 빠르다고 할 수 있지만 최악의 경우(반대로 정렬이 되어있는 경우)에는 N^2으로 거품 정렬만큼 비효율적으로 동작한다.

▶ 공간 복잡도는 O(1)이다. 추가적인 삽입, 삭제 없이 위치를 바꿀 원소를 선택 후 위치만을 변경해주기 때문

▶ Stable Sort이다. Stable Sort란 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되는 정렬이다. 위 예시를 보면 알 수 있듯이 왼쪽 원소와 비교 시 왼쪽 원소가 더욱 큰 값일 때만 교환을 수행하고 동일한 값일 경우 교환을 수행하지 않는다. 따라서 최종적으로 동일한 값들끼리 순서가 유지되게 된다.

물론 구현 방식을 다르게 하여 Unstable sort가 되게 할 수도 있다.

▶ 시간 복잡도를 보면 O(n^2)로 비효율적이라고 하였지만 최선의 경우(정렬이 이미 된 상태)에는 O(N)으로 거품 정렬과 선택 정렬과 비교해서 매우 빠르다고 할 수 있다.

따라서 이미 어느 정도 정렬이 된 리스트일 경우 삽입 정렬을 사용하면 매우 효율적으로 정렬을 수행할 수가 있다.

 

 

 

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void print(vector<int> v, string s);
void insertion_sort(vector<int> v);
void insertion_sort_reverse(vector<int> v);

int main() {
    vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };
    insertion_sort(v);
    insertion_sort_reverse(v);

    return 0;
}


void print(vector<int> v, string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void insertion_sort(vector<int> v) {
    int size = v.size();
    for (int i = 1; i < size; i++) {
        int value = v[i];
        int pos = i - 1;

        while (pos >= 0) {
            if (v[pos] > value) {
                v[pos + 1] = v[pos];
                pos--;
            }
            else {
                break;
            }
        }
        v[pos + 1] = value;
    }
    print(v, "Insertion Sort");
}

void insertion_sort_reverse(vector<int> v) {
    int size = v.size();
    for (int i = 1; i < size; i++) {
        int value = v[i];
        int pos = i - 1;

        while (pos >= 0) {
            if (v[pos] < value) {
                v[pos + 1] = v[pos];
                pos--;
            }
            else {
                break;
            }
        }
        v[pos + 1] = value;
    }
    print(v, "Insertion Sort Reverse");
}

 

결과

 

● print / insertion_sort / insertion_sort_reverse 이 3개의 함수를 정의하였으며 각 함수명에서 기능을 유추할 수 있듯이 출력과 오름차순 삽입 정렬, 내림차순 삽입 정렬 기능을 하는 함수들이다.

 

 

 

● insertion_sort 

 

1. 반복은 index 1부터 시작하며 index 1의 위치한 값과, 그 보다 왼쪽에 있는 원소들 간에 비교를 수행한다.

 

2. 오름차순이기 때문에 작은 수일 수록 왼쪽의 위치해야 한다. 따라서 인접한 왼쪽 값과 비교했을 때 왼쪽에 값이 더욱 클 경우 위치를 교환해준다.

 

3. 이 과정을 반복하여 수행하다 보면 왼쪽에 위치한 원소들끼리는 이미 정렬이 된 상태가 되게 되며, 최종적으로 정렬된 리스트를 얻을 수 있게 된다.

 

 

 

● insertion_sort_reverse 

 

위 오름차순 선택 정렬과 반대로 내림차순 선택 정렬을 수행하는 함수이다.

 

동작 방식은 동일하며 내림차순이기 때문에 인접한 왼쪽 값과 비교할 때 왼쪽의 값이 더욱 작을 경우 교환을 수행 함으로써 내림차순으로 정렬이 되게 된다.