5. 삽입 정렬(Insertion Sort)

삽입 정렬의 개념

차례로 하나씩 꺼내서 앞에 있는 값들과 크기를 비교한 뒤 바꿔서 삽입한다고 해서 삽입 정렬이라 부른다.

 

▼ 삽입 정렬 알고리즘 도식화

그림을 보면 교환이라기 보다는 옆으로 꺼내두는 모습을 볼 수 있는데

삽입 정렬의 구현 방법은 이동(Shift) 방식과 교환(Swap) 방식 둘 다 가능하다.

삽입 정렬의 성능[O(n²)]

정렬할 자료의 수의 제곱에 비례하여 늘어난다.

 

삽입 정렬은 범위를 늘려가면서 비교하는 방식 때문에 배열이 길어지면 길어질 수록 효율이 떨어진다.

반대로 말하면 배열이 짧으면 짧을수록 속도가 빠르다.

 

고성능 정렬 라이브러리에서는 데이터의 양이 적을 때엔 삽입 정렬로 전환하여 속도를 올리기도 한다.

C99

▼ 관련 개념

Condition & Loop & Pointer & Call By Address

 

▼ 구현 코드

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

// 이동 방식
void InsertionSort(int iArr[], int length) {
    int i, j;
    for (i = 1; i < length; ++i) {
        int temp = tArr[i];
        for (j = i; (j > 0) && (tArr[j - 1] > temp); j--)
        {
            tArr[j] = tArr[j - 1];
        }
        tArr[j] = temp;
    }
}

// 교환 방식
void InsertionSort(int iArr[], int length)
{
    for (int i = 1; i < length; i++)
    {
        for (int j = i; (j > 0) && (tArr[j] < tArr[j - 1]); j--)
        {
            Swap(&iArr[j], &iArr[j - 1]);
        }
    }
}

순환문 안에 조건식을 유심히 보자.

 

C/CPP 언어는 조건식 결과가 0인지 아닌지만 확인한다.

그래서 순환문 안에서 조건문을 사용하지 않고 순환문 조건부에서 바로 조건을 확인해도 된다..!

CPP B.11

▼ 관련 개념

Condition & Loop & STD

 

▼ 구현 코드

#include <algorithm>

// 이동 방식
void InsertionSort(int iArr[], int length) {
    int i, j;
    for (i = 1; i < length; ++i) {
        int temp = tArr[i];
        for (j = i; (j > 0) && (tArr[j - 1] > temp); j--)
        {
            tArr[j] = tArr[j - 1];
        }
        tArr[j] = temp;
    }
}

// 교환 방식
void InsertionSort(int iArr[], int length)
{

    for (int i = 1; i < length; i++)
    {
        for (int j = i; (j > 0) && (tArr[j] < tArr[j - 1]); j--)
        {
            std::swap(iArr[j], iArr[j - 1]);
        }
    }
}

CPP A.98 <algorithm> 라이브러리를 사용한 방법이다.

CPP A.11

▼ 관련 개념

Condition & Loop & Template & STD

 

▼ 구현 코드

#include <utility>

// 이동 방식
template<typename T, typename L>
void InsertionSort(T tArr[], L length) {
    int i, j;
    for (i = 1; i < length; ++i) {
        int temp = tArr[i];
        for (j = i; (j > 0) && (tArr[j - 1] > temp); j--)
        {
            tArr[j] = tArr[j - 1];
        }
        tArr[j] = temp;
    }
}

// 교환 방식
template<typename T, typename L>
void InsertionSort(T tArr[], L length)
{
    for (int i = 1; i < length; i++)
    {
        for (int j = i; (j > 0) && (tArr[j] < tArr[j - 1]); j--)
        {
            std::swap(tArr[j], tArr[j - 1]);
        }
    }
}

주조(Template)를 사용하여 어떤 변수형이 오더라도 비교하고 정렬할 수 있는 코드가 되었다.

배열의 길이가 int형이 아닌 long이나 long long으로 오더라도 문제없이 작동한다.

 

CPP A.11에서는 std::swap 함수가 <utility>로 이동했다.