[C++ STL] sort, stable_sort 함수

C++ STL에서는 O(NlogN)의 시간 복잡도를 보장하며 원소를 정렬하는 std::sort 함수, std::stable_sort 함수를 제공한다.

제공하는 함수를 사용하기 위해서는 <algorithm> 헤더 파일 선언이 필요하다.

sort 함수는 3개의 인자를 가진다.

#include <algorithm>

// typename TYPE
void std::sort(TYPE start, TYPE end, Bool compare_func);

첫 번째 인자로는 정렬을 시작할 주소값 (start 부터 시작), 두 번째 인자로는 정렬을 마칠 주소값 (end 전 까지 정렬), 세 번째 인자로는 정렬의 기준이 되는 함수가 들어간다. [start, end)의 범위를 정렬.
세 번째 인자를 비우고 함수를 호출할 경우 기본값으로 오름차순 정렬 함수가 들어간다.

#include <iostream>
#include <algorithm>
using namespace std; // 'std' namespace 사용

bool cmp(int A, int B) {
    return A > B;
}

int main(void) {
    int Array[10] = { 0, 1, 2, 3, 4, 9 ,8, 7, 6 ,5 };
    sort(Array, Array + 10); // default 함수로 정렬(오름차순)
    for (int i = 0; i < 10; i++)
        cout << Array[i] << " ";
    cout << endl;
    sort(Array, Array + 10, cmp); // 직접 정의한 cmp함수로 정렬(내림차순)
    for (int i = 0; i < 10; i++)
        cout << Array[i] << " ";
    return 0;
}

출력 결과

정렬의 기준이 되는 함수는 "strict weak ordering"이라는 조건을 만족하여야 한다.
정의하는 방법은 다음과 같다.

bool Cmp1(int A, int B) { // 오름차순 정렬 함수
	return a < b; // 같은 값을 비교하는 경우 false를 return하게끔 구성
}

bool Cmp2(int A, int B) { // 내림차순 정렬 함수
	return a > b;
}

std::sort 함수는 데이터의 수가 증가함에 따라 insertion sort ➞ quick sort ➞ heap sort를 이용하기 때문에 안정된 정렬을 보장하지 않는다.
따라서 안정된 정렬을 사용하고 싶다면 merge sort을 이용하는 std::stable_sort를 사용하는 것이 좋다.

#include <algorithm>

// typename TYPE
void std::stable_sort(TYPE start, TYPE end, Bool compare_func);

std::stable_sort의 사용 방법은 std::sort 함수와 같다.