C++ stl sort

Sort 함수

• sort 알고리즘은 <algorithm> 헤더 파일에 속함
• sort(start, end)를 이용해 [start, end) 범위의 인자를 오름차순으로 정렬
• Quick sort 기반으로 구현되어 있어 O(nlogn)의 평균 시간복잡도를 가짐

 

1차원 배열에서 vector를 사용하는 경우,

→ begin() : 리스트의 시작 주소 리턴

→ end() : 리스트의 끝 주소 리턴(마지막 값보다 한 칸 뒤 위치)

이므로, sort(arr.begin(), arr.end()) 의 형태로 정렬 가능

 

배열에서 쌍으로 값을 저장해야 할 경우(ex. 좌표),

→ vector<pair<[type], [type]>> 사용하면 됨

→ 값을 줄 때는 make_pair(value1, value2) 사용

→ pair에 저장한 값은 .first , .second 로 불러올 수 있음

→ pair에서 sort함수 사용하는 경우 첫번째 원소 기준 정렬 + 첫번째 원소가 동일할 경우 두번째 원소로 정렬

 

예제 - 백준 11651

https://www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

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

int main() {

	int N, x, y;
	vector<pair<int, int>> cor;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		cor.push_back(make_pair(y, x));
	}

	sort(cor.begin(), cor.end());
	
	for (int i = 0; i < N; i++) {
		cout << cor[i].second << " " << cor[i].first << "\\n";
	}
	
	return 0;
}