[C++] sort 함수를 이용하여 오름차순/내림차순 정렬하는 방법

sort 함수를 이용하여 오름차순/내림차순 정렬하는 방법

 

sort() 함수

• 배열 등 컨테이너들의 요소를 정렬하는 함수
• 보통 array나 vector를 정렬할 때 쓰인다.

 

필요한 헤더

• <algorithm> 헤더를 불러와야 사용할 수 있다.

#include <algorithm>

 

기본 포맷

default (1)
template <class RandomAccessIterator>
    void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
    void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• 기본적으로 이터레이터 범위와 Compare 파라미터를 통해 콜백 함수(Callback Function)를 선택적으로 처리할 수 있다.
• [first, last) 구간의 요소들을 정렬시킨다.
  • a[10]의 첫 번째부터 5번째 요소까지 오름차순으로 정렬시키려면 sort(a[0], a[0] + 5);  와 같이 사용하면 된다.

 

오름차순 정렬

방법 1 : 세 번째 인자 생략하기

• sort() 함수의 세 번째 인자를 비울 경우, 오름차순 정렬을 수행한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = { 4, 6, 5, 3, 2, 9, 8, 7 };
    
    sort(v.begin(), v.end());
    for (int i : v) {
        cout << i << " ";
    }
    
    return 0;
}

2 3 4 5 6 7 8 9

 

방법 2 : 비교 함수를 콜백 함수로 사용하기

• 내림 차순 정렬을 위한 비교 함수를 직접 만든 후, sort() 함수의 세 번째 인자를 넣는다.
• sort() 함수는 이 비교 함수를 콜백하여 정렬을 수행한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b) {
    return a < b;
}

int main() {
    vector<int> v = { 4, 6, 5, 3, 2, 9, 8, 7 };
    
    sort(v.begin(), v.end(), compare);
    for (int i : v) {
        cout << i << " ";
    }
    
    return 0;
}

2 3 4 5 6 7 8 9

 

방법 3 : less<자료형>() 임시 객체 사용하기

• sort() 함수의 세 번째 인자에 less<자료형>() 임시 객체를 넣을 경우, 오름차순 정렬을 수행한다.
  • 자료형 부분을 생략하고 사용해도 된다. (C+14부터)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = { 4, 6, 5, 3, 2, 9, 8, 7 };
    
    sort(v.begin(), v.end(), less<int>());
    for (int i : v) {
        cout << i << " ";
    }
    
    return 0;
}

2 3 4 5 6 7 8 9

 

내림차순 정렬

방법 1 : 비교 함수를 콜백 함수로 사용하기

• 내림 차순 정렬을 위한 비교 함수를 직접 만든 후, sort() 함수의 세 번째 인자를 넣는다.
• sort() 함수는 이 비교 함수를 콜백하여 정렬을 수행한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b) {
    return a > b;
}

int main() {
    vector<int> v = { 4, 6, 5, 3, 2, 9, 8, 7 };
    
    sort(v.begin(), v.end(), compare);
    for (int i : v) {
        cout << i << " ";
    }
    
    return 0;
}

9 8 7 6 5 4 3 2

 

방법 2 : greater<자료형>() 임시 객체 사용하기

• sort() 함수의 세 번째 인자에 greater<자료형>() 임시 객체를 넣을 경우, 오름차순 정렬을 수행한다.
  • 자료형 부분을 생략하고 사용해도 된다. (C+14부터)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = { 4, 6, 5, 3, 2, 9, 8, 7 };
    
    sort(v.begin(), v.end(), greater<int>());
    for (int i : v) {
        cout << i << " ";
    }
    
    return 0;
}

9 8 7 6 5 4 3 2

 

greater 와 less, 그리고 타입 추론

• greater의 내부는 다음과 같이 정의되어 있다.

template< class T >
struct greater; (until C++14)
template< class T = void >
struct greater; (since C++14)

 

• 템플릿(template)을 통한 타입(자료형) 추론은 C++14부터 지원된다. C++14 이전 부터는 greater와 less 사용 시, 자료형을 반드시 명시해주고 사용해야 한다.

sort(v.begin(), v.end(), greater<int>()); 
sort(v.begin(), v.end(), greater<>());    // 자료형 생략, C+14 이후부터 사용 가능

• C++14 부터는 기본적으로 템플릿(template) 특수화를 통하여 자료형 생략이 가능하고(생략 후, void로 처리한다.), Compare로 들어오는 파라미터에 대한 자료형 추론이 가능하기 때문에 자료형을 생략하고 사용할 수 있다.

 

(참고) 벡터(vector)와 pair

바로 정렬하기

• pair를 기반으로 만들어진 벡터의 경우, 따로 설정하지 않으면 first, second, third 순으로 차례 차례 오름차순 정렬이 된다.

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> v;

int main() {
    for (int i = 10; i >= 1; i--) {
        v.push_back({i, 10 - i});
    }
    
    sort(v.begin(), v.end());
    
    for (auto it : v) {    // pair<int, int> 대신 auto를 사용할 수 있다.
        cout << it.first << " : " << it.second << '\n';
    }
    
    return 0;
}

1 : 9
2 : 8
3 : 7
4 : 6
5 : 5
6 : 4
7 : 3
8 : 2
9 : 1
10 : 0

 

커스텀 연산자를 이용하여 정렬하기

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> v;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;    // 첫 번째 숫자를 기준으로 내림차순으로 정렬하기
}

int main() {
    for (int i = 10; i >= 1; i--) {
        v.push_back({i, 10 - i});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for (auto it : v) {    // pair<int, int> 대신 auto를 사용할 수 있다.
        cout << it.first << " : " << it.second << '\n';
    }
    
    return 0;
}

10 : 0
9 : 1
8 : 2
7 : 3
6 : 4
5 : 5
4 : 6
3 : 7
2 : 8
1 : 9

 

관련 문제

https://dev-astra.tistory.com/213

[BOJ-11650][C++] 좌표 정렬하기