STL) 정렬과 관련된 함수들 ( sort, stable_sort, inplace_merge, partial_sort, nth_element, is_sorted )

<개요> STL의 sort(정렬)와 관련된 함수에 대해 작성합니다.

<std::sort> std::sort 함수는 지정된 범위에 있는 요소를 내림차순 또는 오름차순 또는 주어진 이항 술어에 맞춰 정렬 합니다. 인자로는 시작과 끝의 인덱스, 생략된 술어를 받으며 반복자는 임의 접근 반복자여야 합니다. vector<int> nvt = { 1,3,2,4,5,7,6,8,10,9 }; std::sort(nvt.begin(), nvt.end()); // 1,2,3,4,5,6,7,8,9,10 std::sort(nvt.begin(), nvt.end(), [](int& _t1, int& _t2) { return _t1 > _t2; }); // 10,9,8,7,6,5,4,3,2,1 list<int> nlist = { 1,3,2,4,5,7,6,8,10,9 }; std::sort(nlist.begin(), nlist.end()); // error, list는 양방향 접근자 입니다 nlist.sort(); // list 전용 sort 멤버 함수로 사용해야 합니다. std::sort엔 규약이 있습니다. 1. 참조된 범위는 유효해야 하고, 모든 포인터는 역참조 가능해야 하며, 시퀀스 내에서 처음 위치에서 마지막 위치까지 도달할 수 있어야 합니다. 2. A > B 가 아니고, B > A 가 아니라면  A 와 B 는 똑같습니다. 그러나 std::sort 는 등가 요소의 상대적 위치가 유지됨을 보증하지 않습니다. 복잡도는 평균 ( N log N ) 입니다. std::sort는 기본 적으로 내에서 quicksort 를 사용하며, introsort 를 사용한다고 합니다. 하지만 재귀가 깊어질수록 heap_sort를 사용한다고 합니다. 링크 : https://stackoverrun.com/ko/q/367396 <std::stable_sort> std::stable_sort는 std::sort 와 다르게 동가 요소의 상대적 위치가 유지됨을 보증합니다. stable_sort 는 사용가능한 메모리양에 따라 복잡도가 달라집니다. 메모리가 충분하다면 (N log N) 복잡도를 가지고 있지만, 최악의 경우 O((N log N)2) 입니다. 일반적으로 std::sort 함수가 std::stable_sort 보다 더 빠릅니다. class A { public: A(int _t1, char _t2) : m_n(_t1), m_c(_t2) {} int getint()const { return m_n; } char getchar()const { return m_c; } private: int m_n; char m_c; }; int main() { A aa[10] = { {1,'a'}, {1,'b'}, {2,'a'}, {2,'b'} , {2,'c'}, {5,'a'}, {5,'b'}, {5,'c'}, {10,'b'}, {10,'a'} }; for (auto& i : aa) cout << i.getint() << " " << i.getchar() << endl; std::stable_sort(aa, aa + 10, [](const A& i, const A& j) { return i.getint() > j.getint(); }); cout << "정렬 후" << endl; for (auto& i : aa) cout << i.getint() << " " << i.getchar() << endl; } <stable_sort 에 의해 원소 순서가 보존 됨> <std::inplace_merge> inplace_merge는 std::merge 와는 다르게 이미 정렬돼있는 두 배열을 합치면서 정렬 하는 방식입니다. 파라미터로 first, middle, end 를 받으며 양방향 반복자 입니다. vector<int> vnt = { 1,3,5,7,9,2,4,6,8,10 }; cout << "정렬 전" << endl; for (auto& i : vnt) { cout << i << endl; } // 1,3,5,7,9,2,4,6,8,10 inplace_merge(vnt.begin(), vnt.begin() + 5, vnt.end()); // middle = vnt.begin() + 5 cout << "정렬 후" << endl; for (auto& i : vnt) { cout << i << endl; } // 1,2,3,4,5,6,7,8,9,10 merge는 두 배열이 정렬이 돼있으나, 합쳐졌을땐 정렬이 되지 않을때 사용됩니다. 예를 들어 vnt 는 [begin, begin+5) 까지는 정렬돼있고 [begin+5, end) 까지도 정렬 돼있습니다. 그러나 [begin, end) 는 정렬이 돼있지 않습니다. 이럴때 사용해야 합니다. inplace_merge의 또다른 사용 예 #include <vector> #include <iostream> #include <algorithm> template<class Iter> void merge_sort(Iter first, Iter last) { if (last - first > 1) { Iter middle = first + (last - first) / 2; merge_sort(first, middle); merge_sort(middle, last); std::inplace_merge(first, middle, last); } } int main() { std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3}; merge_sort(v.begin(), v.end()); for(auto n : v) { std::cout << n << ' '; } std::cout << '\n'; } 출처 : cppreference merge와 inplace_merge의 다른 점 : sort는 그냥 begin부터 end까지 사이의 자료가 뒤죽박죽이어도 잘 정렬되고요.  merge는 begin 부터 middle까지 정렬되있고, middle부터 end까지 정렬되어 있을때 정렬을 해주는겁니다. 예를 들면 [0]1, [1]3, [2]6, [3]9, [4]0, [5]2, [6]4, [7]5, [8]7, [9]8 이렇게 되어 있을때 begin은[0], middle는 [4], end는 [10]입니다.  그럼 begin부터middle까진 정렬이 된거고요. (stl에서 begin, end라고 하면 begin이상 end미만(end제외)라는거 아시죠?)  middle부터end까지 정렬되어 있죠. 그런데 begin에서 end까지는 정렬이 안되어 있고요. 이때 sort를 이용하면 퀵소트 알고리즘으로 정렬을 해서 O(nLogN) 복잡도를 갖고, merge를 이용하면 O(N)복잡도로 정렬이 됩니다.  이경우 sort보다 merge가 훨씬 빠르죠. merge정렬을 아신다면 왜 그런지 이해하실거에요. 그럼 그냥 merge와 inplace merge차이는, 여기서 inplace의 의미는 파라메터로 넘겨준 데이터를 함수 안에서 직접 수정하겠다는 의미입니다. (다른데서도 종종쓰이니 기억해두면 좋습니다.) 그래서 inplace merge는 파라메터로 넘겨준 데이터가 정렬되고, 별도의 리턴값은 없습니다. 그냥 merge는 파라메터로 넘겨준 소스 데이터를 함수 내부에서 위치 이동시키지 않습니다.  그건 그대로 두고 정렬된 데이터를 별도의 저장소에 기록합니다. 원본은 건드리지 않고 별도의 정렬결과를 얻고 싶을때 좋겠죠. 그리고 또나하나의 차이는 inplace merge는 연속된 공간의 begin middle end를 요구하지만 merge는 begin1~end1, begin2~end2로 각각 분리된 두개의 공간를 넣을 수 있습니다. 물론 연속된 하나의 공간을 넣어도 되고요. 연속된 공간일 경우 begin middle end가 begin1=begin, end1=middle, begin2=middle, end2=end가 되겠죠. (분리된 두개의 공간을 파라메터로 받기 때문에 inplace로 정렬을 해줄수도 없습니다.)  출처 : http://fbsight.com/t/c-stl-merge-inplace-merge/152009/2 <std::partial_sort>  partial_sort는 N번째까지만 정렬 한 후, 나머지는 정렬하지 않는 방식입니다. 만약 최상위의 몇 개의 값만 추출해내고 싶을때 유용한 정렬 방법입니다. partial_sort는 안정적이지 않습니다. ( 등가 요소의 위치가 유지됨을 보장하지 않습니다. ) partial_sort의 복잡도는 O (last - first) log (mid - first) 입니다. vector<int> vnt = { 1,3,5,7,9,2,4,6,8,10,1,5,6,8,4,5,3,18,6,5,2,1 }; partial_sort(vnt.begin(), vnt.begin() + 5, vnt.end(),greater<int>()); // 18 10 9 8 8 1 2 3 4 5 1 5 6 6 4 5 3 7 6 5 2 1 <std::nth_element> nth_element는 한 기준을 잡아, 그 기준보다 작은것들은 왼쪽으로 기준보다 큰 것들은 오른쪽으로 정렬 시킵니다. nth_element는 안정적이지 않습니다. ( 등가 요소의 위치가 유지됨을 보장하지 않습니다. ) nth_element의 복잡도는 (last - first) 에 비례합니다. vector<int> vnt = { 1,3,5,7,9,2,4,6,8,10,1,5,6,8,4,5,3,18,6,5,2,1 }; nth_element(vnt.begin(), vnt.begin() + (vnt.size() / 2), vnt.end()); // 기준은 가운데 값인 5로 정했습니다. //1 1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 8 8 9 10 18 <std::is_sorted> 한 컨테이너가 정렬되어 있는지 확인합니다. vector<int> vnt = { 1,2,3,4,5,6,7,8,9,10 }; cout << is_sorted(vnt.begin(), vnt.end(), greater<int>()) << endl; // false cout << is_sorted(vnt.begin(), vnt.end(), less<int>()) << endl; // true