[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬은 임의의 배열을 정리하는 방법으로 알고리즘의 각 반복 단계마다 다음 원소를 현재의 정렬된 배열 부분에 삽입한다. 삽입 정렬은 두 번째 원소부터 시작한다. 만약 두 번째 원소가 첫 번째 원소보다 작다면 두 원소의 위치를 바꾼다. 그리고 다음 원소로 넘어간다. 만약 세 번째 원소가 두 번째 원소보다 작다면 위치를 바꾸고, 첫 번째 원소보다 작다면 위치를 또 바꾼다. 배열의 각 원소에 대해 원소의 적정 위치에 도달할 때까지 왼쪽으로 교체를 반복한다.

C++ 구현

template <class RandomIt>
void insertion_sort(RandomIt first, RandomIt last)
{
    for (RandomIt it = first+1; it != last; ++it)
    {
        int i = it-first;
        while (i>0 and *(first+i-1) > *(first+i))
        {
            auto temp = *(first+i);
            *(first+i) = *(first+i-1);
            *(first+i-1) = temp;
            --i;
        }
    }
}

template <class RandomIt, class Compare>
void insertion_sort(RandomIt first, RandomIt last, Compare comp)
{
    for (RandomIt it = first+1; it != last; ++it)
    {
        int i = it-first;
        while (i>0 and comp(*(first+i-1), *(first+i)))
        {
            auto temp = *(first+i);
            *(first+i) = *(first+i-1);
            *(first+i-1) = temp;
            --i;
        }
    }
}

[first, last) 범위의 원소를 오름차순으로 삽입 정렬하는 코드이다. 두 번째 버전을 이용하면 두 원소를 매개변수로 하는 bool형 함수를 대입하여 다른 순서로 정렬할 수 있다.