[C++] 정렬 함수 : sort()

sort() 는 배열 등 컨테이너들의 요소를 정렬하는 함수이다. 보통 array나 vector를 정렬할 때 쓰이며 O(nlogn)의 시간복잡도를 가진다. sort()의 parameter는 3가지인데 이 중 2개는 필수로 넣어야한다.

즉 sort() 함수는 두 가지 형태로 오버로딩 되어 있다.

template <typename T>
void sort(T start, T end);

template <typename T>
void sort(T start, T end, Compare comp);

 

또한 범위는 [first, last) 이다. 즉 크기가 5인 배열을 sort하고 싶다면 sort(a, a+5) 라고 하면 된다. 구체적인 사용 예시는 아래 코드를 확인하자.

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

int main() {
	int a[5] = {5,1,2,3,4};
	
	sort(a, a+5);
	for(int i:a) cout << i << endl;

	sort(a, a+5, greater<int>());
	for(int i:a) cout << i << endl;
}

 

추가로 pair를 기반으로 만들어진 vector를 정렬하면 first, second 순으로 차례차례 오름차순 정렬된다.

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

int main() {
	vector<pair<int, int>> v;
	v.push_back({2, 7});
	v.push_back({3, 8});
	v.push_back({1, 9});
	
	sort(v.begin(), v.end());
	for(auto i:v) cout << i.first << ' ' << i.second << endl;
}

 

커스텀 함수를 넣지 않으면 기본적으로 오름차순이며 comp 자리에 greater<int>() 를 넣어 내림차순으로 정렬할 수도 있다. 오름차순, 내림차순을 정의하기 위해 comp를 아래와 같이 정의해서 사용해도 된다.

bool comp(int a, int b) {
	return a < b;
} // 오름차순

bool comp(int a, int b) {
	return a > b;
} // 내림차순