정렬 알고리즘 공부를 하다보면, 불안정 정렬과 안정 정에 대해서 공부하게 된다.
정렬 알고리즘이 안정적이라는 것은, 정렬 키가 같은 요소들 사이의 원래 순서가 유지된다는 것을 의미한다.
예를 들어 사람 정보를 정렬하고자 하는 상황에서 정렬 기준이 이름이라고 할 때, 두 사람의 이름은 같아도 실제로는 다른 사람이다.
만약 A,B사람이 둘다 이름이 동일할 때, 기존 배열에 A가 B보다 앞쪽 원소에 있을 때 정렬 후에도 A가 B보다 앞쪽에 있음을 보장하면 안정정렬이다.
(즉, int같은 기본타입에서는 그 값 자체로 정렬기준이므로 큰 의미가 없다)
C++에서 원소들을 정렬을 할 때 일반적으로 sort() 함수를 호출한다.
결론부터 말하면, C++에서 제공하는 sort()함수는 불안정 정렬이다.
sort() vs stable_sort()의 사용 알고리즘
정렬이 안정 정렬이냐 불안정 정렬이냐는 어떠한 정렬 알고리즘을 사용했냐에 따라 달라진다.
그러면 sort()와 stable_sort()는 각각 어떤 정렬 알고리즘을 사용할까?
이는 사실 C++ 표준에 sort()에 어떤 알고리즘을 사용하라고 표준이 잡혀있지는 않다.
하지만 대부분의 구현체 (libstdc++ (GCC), libc++ (Clang), MSVC STL (Microsoft Visual C++))
에서는
sort() : IntroSort (인트로 정렬)
stable_sort() : MergeSort (병합정렬)
을 사용한다고 한다.
인트로 정렬은 생소해서 찾아보니,
인트로 정렬(introsort)은 평균적으로 빠른 성능을 내면서 최악의 조건에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다. 퀵 정렬로 시작한 다음 재귀 깊이가 정렬 대상 요소의 수의 레벨(로그)을 초과할 때 힙 정렬로 전환하며 요소들의 수가 특정 임계치 미만일 때 삽입 정렬로 전환한다. 3가지 알고리즘의 좋은 부분을 합쳐놓은 것이며 인트로 정렬이 사용하는 이 3가지 알고리즘들은 비교 정렬이기 때문에 인트로 정렬 또한 비교 정렬이다.
이라고 한다 (참고 링크)
궁금해서 실제 코드를 찾아보니
libstdc++는 sort()함수 구조가 아래와 같이 되어 있다 (링크)
template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}introsort()를 호출함을 알 수 있다.
그 다음줄에 삽입 정렬을 한번 더 호출하는데, 구글링해보니
인트로 정렬은 퀵소트를 사용하다가 힙정렬로 전환하고 정렬 대상이 작아지면
삽입 정렬로 처리한다고 한다.
참고로 삽입 정렬의 특징이, 평균 시간복잡도는 높아도,
만약 거의 다 정렬이 되어 있는 상태에서는 정렬 속도가 빠르다는 장점이 있다는 것을 기억하자.
실제 사용 예 (PS)
알고리즘 문제를 풀 때도 활용할 수 있다.
그 예시로 백준 10814 - 나이순 정렬 문제에서 활용해볼 수 있다.
문제에서 나이 오름차순, 그리고 나이가 같으면 문제에서 입력한 순서대로 정렬한다고 되어있다.
따라서 입력한 순서대로 벡터 등의 컨테이너에 원소를 순서대로 추가하고,
stable_sort()를 호출하면 된다.
