배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다.
sort()는 기본적으로 <algorithm> 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 <algorithm> 헤더파일을 가져와야한다.
#include <algorithm>
1) 배열(array)
배열을 정렬할 때는 sort()를 아래와 같이 사용한다.
sort(시작주소, 끝주소 + 1)
시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다.
2) 벡터(vector)
벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다.
sort(v.begin(),v.end())
여기서 v는 정렬하고 싶은 벡터의 이름을 의미한다. 참고로 end() 함수는 끝주소 + 1 값을 반환하므로 뒤에 +1을 붙이지 않아도 된다.
sort()는 기본적으로 오름차순으로 정렬을 하지만, 다른 기준으로 정렬을 해야할 때도 있다. 그럴 때에는 새로운 함수를 정의해줘야한다. 그 함수를 compare()이라고 할 때 아래와 같이 사용한다.
sort(시작주소, 끝주소 + 1,compare)
예를 들어 왼쪽에 있는 변수가 오른쪽의 있는 변수보다 크도록 하는 내림차순으로 정렬하고 싶을 경우는 아래와 같이 함수를 정의할 수 있다.
bool compare(int var1, int var2)
{
return var1 > var2;
}
여기서 var1은 배열의 왼쪽에 있는 값을 나타내고 var2는 배열의 오른쪽에 있는 값을 나타낸다.
pair을 담는 배열을 정렬하는 경우에는 기본적으로 첫 번째 값을 기준으로 오름차순을 한다. 그런데 만약 첫 번째 값과 두 번째 값의 합을 기준으로 오름차순을 하고 싶으면 아래와 같이 함수를 정의할 수 있다.
bool compare(pair<int, int> p1, pair<int, int> p2)
{
return p1.first + p1.second < p2.first + p2.second;
}
'정보 > 알고리즘&자료구조' 카테고리의 다른 글
LIS 알고리즘(최장 증가 부분 수열) O(nlogn) (0) | 2024.05.26 |
---|---|
최장 증가 부분 수열 DP O(N^2) (1) | 2024.02.07 |
Knapsack Problem Dynamic Programming C++ (1) | 2024.02.01 |