#stl 정렬 알고리즘(sort, stable_sort, partial_sort, nth_element)

컨테이너 정렬이 필요할 때, sort를 사용하고 순서가 유지돼야 하면 stable_sort를 사용했다. partial_sort와 nth_element는 한 번도 사용해본 적이 없는데, 일부분만 정렬이 필요하거나 몇 번째 원소를 뽑을 때 유용하게 사용할 수 있을 것 같다. 예를 들면 최고 작은 수 10개만 차례대로 혹은 차례 상관없이 뽑는다던지, 9번째로 작은 수만 뽑는다던지 할 때에 사용하면 좋을 거 같다. 구현하는데 시간을 추가로 쓰는 것도 아니고 이미 구현되어 있는데, 딱 필요한 만큼만 정렬해서 시간을 절약할 수 있다. 아무리 작은 시간이라 하더라도 그냥 낭비하는 건 죄를 짓는 거.

nth_element는 정렬 기준에 따라 몇 번째 원소만 정확히 뽑아준다. 원소를 기준으로 정렬 기준에 맞게 좌우를 나눠주기는 하는데, 그 원소들 사이에 정렬은 되어 있지 않은 상태이다. partial_sort는 시작점부터 지정한 위치까지만 정렬해준다. 나머지는 정렬되지 않은 상태로 놔둔다. sort와 stable_sort는 시작점에서 끝점까지 정렬하는데, 정렬되고 난 뒤 stable을 보장 여부가 다르다. 동일한 정렬 기준을 가진 녀석들의 순서가 정렬 후에도 바뀌지 않으면 stable하다고 하는데, 뒤에 소스 코드 예를 보면 단박에 이해된다. 참고로 merge sort, insertion sort가 대표적인 stable sort 알고리즘이고 unstable sort의 대표적인 알고리즘은 quicksort다.

수행 시간은 nth_element < partial_sort < sort < stable_sort 이다.

sort, stable_sort, partial_sort 테스트 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

struct Item
{
    int     num;
    char    tag;

    explicit Item(int n, char t = ' ') : num(n), tag(t) {}
};

inline bool operator< (const Item& lhs, const Item& rhs)
{
    return lhs.num < rhs.num;    // 숫자만 비교한다.
}

inline std::ostream& operator<< (std::ostream& ost, const Item& item)
{
    ost << item.num << item.tag;
    return ost;
}

정렬 알고리즘에서 호출해주는 operator < 는 숫자만 비교한다. tag는 stable하게 정렬되는지 확인하는 용도로 사용한다.

int main()
{
    const Item itemArray[40] =
        {
            Item (-4, ' '), Item (16, ' '),
            Item (17, ' '), Item (-3, 's'),
            Item (14, ' '), Item (-6, ' '),
            Item (-1, ' '), Item (-3, 't'),
            Item (23, ' '), Item (-3, 'a'),
            Item (-2, ' '), Item (-7, ' '),
            Item (-3, 'b'), Item (-8, ' '),
            Item (11, ' '), Item (-3, 'l'),
            Item (15, ' '), Item (-5, ' '),
            Item (-3, 'e'), Item (15, ' '),
            Item (-4, ' '), Item (16, ' '),
            Item (17, ' '), Item (-3, 's'),
            Item (14, ' '), Item (-6, ' '),
            Item (-1, ' '), Item (-3, 't'),
            Item (23, ' '), Item (-3, 'a'),
            Item (-2, ' '), Item (-7, ' '),
            Item (-3, 'b'), Item (-8, ' '),
            Item (11, ' '), Item (-3, 'l'),
            Item (15, ' '), Item (-5, ' '),
            Item (-3, 'e'), Item (15, ' ')
        };

    typedef std::vector<Item> ItemVector;

    ItemVector v0(
        itemArray, itemArray + sizeof(itemArray) / sizeof(itemArray[0]));
    ItemVector v1(v0.begin(), v0.end());
    ItemVector v2(v0.begin(), v0.end());

    std::sort (v0.begin(), v0.end());
    std::stable_sort (v1.begin(), v1.end());
    std::partial_sort (v2.begin(), v2.begin() + 10, v2.end());

    std::cout << "### sort(begin, end)\n";
    std::copy (v0.begin(), v0.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### stable_sort(begin, end)\n";
    std::copy (v1.begin(), v1.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### partial_sort(begin, begin+10, end)\n";
    std::copy (v2.begin(), v2.end(), std::ostream_iterator<Item>(std::cout, " "));

    return 0;
}

20개 정도로 하니깐 sort로 정렬해도 결과가 stable해서 40개로 늘렸다. VS2005의 딩컴웨어 STL에서는 원소 개수가 32개 보다 작으면 insertion sort를 하기 때문에 20개로 sort를 호출하면 stable한 결과가 나온다. 정렬 알고리즘은 원소를 변경하기 때문에 복사해서 똑같은 원소를 가진 벡터를 3개 만들고 각각을 정렬한 다음 출력했다.

sort 함수는 stablestable의 순서가 엉켜있고 stable_sort 함수는 제대로 출력하고 있다. partial_sort 함수는 [begin, begin+10) 까지만 정렬을 한다.

nth_element 테스트 소스 코드

nth_element 같은 경우는 위와 같은 예제로 하면 확인이 어려워 따로 테스트 코드를 만들었다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

int main()
{
    // VS 2005에서 원소 개수가 32개 이하면 Insertion sort를 한다.
    static const int INSERTION_SORT_THRESHOLD = 33;
    std::vector<int> v;
    v.reserve(INSERTION_SORT_THRESHOLD);

    for (int i = 0; i < INSERTION_SORT_THRESHOLD; ++i)    v.push_back(i);
    std::random_shuffle(v.begin(), v.end());

    std::cout << "### before\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    std::cout << "### nth_element(begin, begin+12, end)\n";
    std::nth_element(v.begin(), v.begin()+12, v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

VS 2005의 딩컴웨어 STL 구현을 보면 분할 정복 알고리즘(Divide and conquer algorithm)을 사용해서 구현했는데, 여기서도 sort와 같이 분할한 구역 원소 개수가 32개 이하이면 insertion sort을 한다. 그래서 출력해보면 12 앞에 숫자들이 정렬된 상태로 보인다. 처음에 원소를 10개로 잡아 놓고 테스트를 했는데, 전체가 정렬돼서 무척 의아했다. 궁금해서 소스코드를 보니 원소 개수가 32개 이하이면 insertion sort로 정렬하더라.

STLport 5.1.3 으로 돌려본 결과. insertion sort를 하는 threshold가 3이다.

참고

• Effective STL 항목 31
• C++ Standard Library 튜토리얼,레퍼런스