c++에서는 자료를 정렬하기 위해 STL에서 지원하는 함수 2개를 사용할 수 있다. Sort()와 Stable_Sort()이다.
우선 두 함수를 사용하기 위해서는 algorithm 헤더를 include해주어야 한다.
#include <algorithm>Sort
sort()는 인트로 정렬(Intro Sort)이라는 정렬 방식을 바탕으로 구현되어 있다. Intro Sort란 퀵 정렬(Quick Sort)를 기반으로 힙 정렬(Heap Sort)과 합 정렬(Insertion Sort)을 섞은 방식으로 최악의 경우 O(N^2)의 시간복잡도를 가지는 퀵 정렬과 다르게, 최악의 경우에도 O(n log n)을 보장하는 정렬 알고리즘이다.
sort(array.begin(), array.end(), compare);sort()는 기본적으로 정렬하고자 하는 배열의 시작과 끝 그리고 정렬 기준을 인수로 넘겨주어 사용할 수 있다. compare의 값을 넣지 않는 경우에는 기본적으로 오름차순으로 정렬된다.
// 오름차순
sort(array.begin(), array.end(), less<int>());
// 내림차순
sort(array.begin(), array.end(), greater<int>());미리 정의되어 있는 compare함수를 이용하여 오름차순과 내림차순으로 정렬할 수 있다.
sort()를 사용하며 주의해야 할 점은 sort()는 불안정 정렬(unstable sort)이라는 것이다.
예시로 3, 4, 3, 5, 2 해당 배열을 sort()를 이용하여 정렬해보자.
> test 1
2 3(*) 3 4 5
> test 2
2 3 3(*) 4 5이처럼 같은 값을 가지는 원소들의 정렬이 불안정하여 입력순으로 정렬 될지 아닐지 예상할 수 없다.
Stable_Sort
stable_sort()는 병합 정렬(Merge Sort)라는 정렬 방식으로 구현되어 있고, O(n log n)의 시간복잡도를 보장한다.
stable_sort(array.begin(), array.end(), compare);기존 sort 함수와 동일하게 배열의 시작과 끝 그리고 정렬 기준을 인수로 넘겨주어 사용할 수 있다. compare의 값을 넣지 않는 경우에는 기본적으로 오름차순으로 정렬된다.
// 오름차순
stable_sort(array.begin(), array.end(), less<int>());
// 내림차순
stable_sort(array.begin(), array.end(), greater<int>());기존 sort 함수와 동일하게 미리 정의되어 있는 compare함수를 사용할 수 있다.
기존 sort 함수와 다른 점은 이름에서도 유추할 수 있듯이 stable_sort는 안정 정렬(Stable Sort)이라는 것이다. 병합 정렬은 같은 값을 가진 원소의 순서를 보장하여주기 때문에 stable_sort는 안정된 정렬이 된다.
