[알고리즘] 선택 정렬(Selection Sort)

선택 정렬은 n개의 원소를 가진 배열에서 i 번째 단계에서 [i, n) 번째 원소 중에 최소값을 구해 i 번째 원소와 위치를 바꾼다.

특성

일반적으로 각 i번째 과정이 끝나면 앞에서 i개의 원소들은 최종 위치에 도달한 것이다.

C++ 구현

template <class RandomIt>
void selection_sort(RandomIt first, RandomIt last)
{
    for (RandomIt it1 = first; it1 != last-1; ++it1)
    {
        RandomIt min = it1;
        for (RandomIt it2 = it1+1; it2 != last; ++it2)
            if (*it2 < *min) min = it2;
        auto temp = *it1;
        *it1 = *min;
        *min = temp;
    }
}

template <class RandomIt, class Compare>
void selection_sort(RandomIt first, RandomIt last, Compare comp)
{
    for (RandomIt it1 = first; it1 != last-1; ++it1)
    {
        RandomIt min = it1;
        for (RandomIt it2 = it1+1; it2 != last; ++it2)
            if (comp(*it2,*min)) min = it2;
        auto temp = *it1;
        *it1 = *min;
        *min = temp;
    }
}

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