[C++] STL - sort

STL에서 제공하는 sort 함수를 알아보자.

 

우선 sort 함수를 이용하기 위해서는 <algorithm> 헤더 파일을 include 해주어야 한다. 

sort함수는 퀵정렬을 기반으로 하므로 O(nlogn)의 평균 시간 복잡도를 가진다. 

 

sort 함수의 형태는 아래와 같다.

 

template<typename T>
void sort(T start, T end); //default 오름차순
 
template<typename T>
void sort(T start, T end, Compare comp); //compare 함수 정의 가능

위처럼 정렬 기준이 되는 함수 (comp) 를 추가하지 않는다면 기본적으로 '오름차순'으로 정렬해준다. 

 

#include<algorithm>
 
using namespace std;
 
vector<int> v;
 
sort(arr, arr+n);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>()); //내림차순
sort(v.begin(), v.end(), less<int>()); //오름차순
 
sort(v.begin(), v.end(), compare); //사용자 정의 함수
 
bool compare(int a, int b){
    return a>b;
}

사용 방법은 위와 같다. 

1. sort(start, end)를 이용하여 [start, end) 범위에 있는 인자(element)를 오름차순(default)로 정렬한다.

 

2. 정렬 기준을 바꾸고 싶다면 STL에서 제공하는 함수(greater, less)등을 이용해도 된다.

단, 이 경우에는 <functional> 헤더를 추가해주고, 함수를 세번째 인자 위치에 넣어준다.

 

3. 직접 정렬 기준을 정하고 싶다면 bool 반환형의 함수를 정의하면 된다.

위의 예시에서는 a>b인 경우 true를 반환하기 때문에 내림차순으로 정렬이 된다. 

 

아래는 실제 예시이다. 

#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
 
bool compare(int a, int b) {
    return abs(a) < abs(b); //절댓값의 오름차순
}
 
int main(void) {
    int arr[10] = { 3, -5, 1, 8, -9, 6, -2, 3, 4, 11 };
    sort(arr, arr + 10); //오름차순
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';
    cout << '\n';
    
    sort(arr, arr + 10, greater<int>()); //내림차순
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';
    cout << '\n';
 
    sort(arr, arr + 10, compare); //사용자 정의 함수
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';
    cout << '\n';
}
 

이처럼 사용자 정의 함수를 이용하여 여러 변수를 담고 있는 구조체 등도 특정 기준으로 정렬이 가능하다.