[Algorithm] [Sort] Insertion Sort

삽입 정렬이란 데이터가 들어가야할 위치를 찾아 그곳에 삽입하여 정렬을 한다.

이 글은 기본적으로 삽입정렬이 뭔지 아는 사람들을 위해 작성되었다.

삽입정렬이 정렬이 되는 원리를 말해보자면

데이터가 N개 있을떄 N-1개만 위치를 잡아주면 나머지 1개는 알아서 정렬이 될테고,

자신이 삽입될 위치에 삽입하게되면, 나머지 원소들의 연산에 의해 정렬이 완료된다.

기본적인 삽입정렬 코드는 다음과 같다.

void InsertionSort2(int* arr, int sz) {  
    int i, j;
    int temp;
    for (i = 1; i < sz; i++) {
        j = i - 1;
        temp = arr[i];
        while (j >= 0 && arr[j]>temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

너무 간단한 부분이라 넘어가겠다.

손수 직접 배열을 밀어주는데, memcpy나 memmove를 이용해서 작성한 소스는 다음과 같다.

void InsertionSort3(int* arr, int sz) {  
    int i, j;
    int temp;
    for (i = 1; i < sz; i++) {
        j = i - 1;
        temp = arr[i];
        while (j >= 0 && arr[j]>temp) {
            j--;
        }
        memcpy(arr + j + 2, arr + j + 1, (i - j - 1) * sizeof(int));
        arr[j + 1] = temp;
    }
}

하지만 역시 그게 그거다.

실제로 속도갱신도 그렇게 빨라지지 않는다.

왜냐면 바로 배열을 미는것이 아닌, 밀어야할 시작점을 찾는데 while이 돌기 때문.

여기서 , 위의 소스들에서 i 가 반복자인데, 반복문을 돌때 0부터 i까지 는 정렬이 완료되어있음을 증명할 수 있다.

정렬이 되어있으면, 원소가 삽입될 위치를 이진탐색으로 찾을 수 있고,

같은 방법으로 memcpy나 memmove로 밀면 더욱 속도가 개선될것이라 생각된다.

하지만, 일반적인 이진탐색이 아닌 마치 C++ 의 std::lower_bound 를 구현하면된다.

lower_bound는 해당 원소가 삽입되야할 위치를 반환한다.

이를 구현해보면 다음과 같다.

int lower_bound1(int* arr, int sz, int key) {  
    int L = 0;
    int R = sz - 1;
    int M = (L + R) >> 1;
    if (arr[0] > key)return 0;
    if (arr[R] < key)return sz;
    while (L <= R) {
        if (arr[M] == key)return M;
        else if (arr[M] < key)L = M + 1;
        else R = M - 1;
        M = (L + R) >> 1;
    }
    return M + 1;
}
void InsertionSort1(int* arr, int sz) {  
    int i = 0;
    int temp = 0;
    int idx = 0;
    while (i < sz) {
        temp = arr[i];
        idx = lower_bound1(arr, i, temp);
        memcpy(arr + idx + 1, arr + idx, (i - idx) * sizeof(int));
        arr[idx] = temp;
        ++i;
    }
}

그래도 복잡도는 O(n^2) 이지만, 앞의 삽입정렬보다는 개선이 되었음은 분명하다.

이를 여러 조건에서 측정해보자

엄청나게 압도적인 속도이다.

이미 정렬이 되어있는 경우를 제외하고, 모든 경우에서 다른 삽입정렬을 압도한다.

그럴수 밖에 없는게, 일반적인 삽입정렬은 이미 정렬이 되어있는경우 순수N이기 떄문에..

이진 삽입 정렬은 lower_bound의 logn 시간을 반드시 소모한다....

삽입정렬은 버블이나 선택정렬과는 다르게

퀵소트를 개선할때 사용된다. 따라서 본 방법은 반드시 기억하자.