정렬
PS를 하다보면 데이터를 정렬한 뒤 다뤄야 하는 상황이 생긴다.
보통 이런 경우에 시간복잡도가 빠른 퀵정렬(quick sort)를 사용하는데 당연히 매번 구현하기는 번거로움으로 algorithm헤더에 이미 구현되어 있는 sort함수를 사용한다.
모든 STL의 단점이지만 미리 구현되어 있는 만큼 특정 상황에서 유동적으로 활용하려면 그에 해당하는 사용법을 외우고 있어야 된다.
사용법
1. 배열에서 사용법
sort 함수의 원형은 다음과 같다.
void sort (RandomAccessIterator first, RandomAccessIterator last);#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
int arr[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}첫번째 인자로는 정렬 하는 배열의 첫 주소
두번째 인자로는 정렬 하는 배열의 끝 주소
를 적어주면 기본 오름차순으로 정렬된다.
내림차순으로 정렬하기 위해서는 functional 헤더에 있는 greater<int>를 사용하면 되지만,
이보다 더 범용적으로 사용할 수 있는 방법이 있으므로 이는 3과 4에서 소개하도록 하겠다.
2. 벡터에서 사용법
vector container도 sort함수를 사용하여 정렬할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i];
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) cout << vec[i] << " ";
return 0;
}배열과 마찬가지로
첫번째 인자로는 정렬 하는 벡터의 첫 주소
두번째 인자로는 정렬 하는 벡터의 끝 주소가 온다.
vector cotainer는 이를 반환하는 함수인 begin, end가 있기 때문에 이를 사용하였다.
3. 연산자 오버로딩 (구조체 정렬)
특정 상황에서 데이터를 구조체로 묶어서 다루고, 그에 따라 새로운 비교 방식을 필요로 한다.
연산자 오버로딩은 기존에 존재하지 않았던 구조체끼리 대소비교 연산을 정의함으로써
sort함수가 문제 없이 작동하도록 해준다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int x, y;
bool operator<(node a) {
if (x == a.x) return y < a.y;
return x < a.x;
}
};
int main() {
int n;
cin >> n;
vector<node> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i].x >> vec[i].y;
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) cout << vec[i].x << " " << vec[i].y << endl;;
return 0;
}위 코드는 node 구조체를 자료형으로 가지는 벡터를 정렬하는 예제이다.
sort함수 부분을 바뀌지 않았지만 구조체 선언 부분에서 네줄의 코드가 새로 추가 된 것을 확인할 수 있다.
bool operator<(node a) {
if (x == a.x) return y < a.y;
return x < a.x;
}이는 < (대소비교 연산자)를 새롭게 정의하는 코드이다.
< 연산자에서 왼쪽에 오는 구조체를 기본 구조체라고 하자
a는 기본 구조체와 비교되는 외부 구조체를 뜻한다. (연산자 오른쪽)
멤버 변수 이름을 그냥 적으면 기본 구조체 내부 멤버 변수이고
a. 을 하고 호출하면 외부 구조체 내부의 멤버 변수이다.
만약 헷갈린다면 연산자 오버로딩을 구조체 밖에서 해도 상관없다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int x, y;
};
bool operator<(node a, node b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int main() {
int n;
cin >> n;
vector<node> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i].x >> vec[i].y;
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) cout << vec[i].x << " " << vec[i].y << endl;;
return 0;
}이러한 경우에는 구조체 밖으로 연산자 정의를 옮겼기 때문에 기본 구조체도 연산자에 넘겨주어야 한다.
4. compare 함수
연산자 오버로딩의 문법이 익히기 힘들다면 sort 함수는 두번째 사용법을 보자.
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int x, y;
};
bool comp(node a, node b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int main() {
int n;
cin >> n;
vector<node> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i].x >> vec[i].y;
sort(vec.begin(), vec.end(), comp);
for (int i = 0; i < n; i++) cout << vec[i].x << " " << vec[i].y << endl;;
return 0;
}3번의 연산자 오버로딩을 외부에서 했을 때와 굉장히 유사하다.
이 코드 같은 경우에는 직접 정렬하는 데이터를 비교할 수 있는 함수를 sort 함수에게 3번째 인자로 넘겨주는 방법이다.
정리
sort 함수를 다양하게 활용할 수 있는 방법에 대해 알아보았다.
대부분 기능이 똑같지만 다른 문법을 사용해서 생각보다 헷갈리고 외우기 어렵다.
그렇기 때문에 다양한 코딩 방식(연산자 오버로딩, compare 함수) 중 본인이 외우기 편한 방식을 하나 선택해서 기억하는 것이 좋다.
필자와 같은 경우는 2번과 3번을 주로 사용한다.