c++ stl SORT 사용법

문제풀다가 빡쳐서 씀

 

Sort

• [first,last)범위 내에 있는 원소들을 오름차순으로 정렬해주는 알고리즘이다
• 값이 동일한 요소에 대해서는 원래 상대적인 순서 (인덱스번호)를 장담하지 못한다 -> stable sort  로 해결 가능

 

• 배열 : sort(arr , arr+N)

• 벡터 : sort(v.begin() , v. end())

• 사용자 정의 함수를 따로 사용할 수 있다. 뒤에 사용자 정의함수를 적으면 된다. 
  무엇을 기준으로 대소관계를 가릴 것인지 적어주는 것이다. 

예를 들어, 백준 1181번 단어정렬 (www.acmicpc.net/problem/1181)같은 경우 

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

vector <string> arr;
int n;

bool comp(string i, string j) {
	if (i.size() == j.size()) return i < j;
	return i.size() < j.size();
}

int main() {
	scanf("%d ", &n);
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		getline(cin, arr[i]);
	}
	sort(arr.begin(), arr.end(),comp);
	for (int i = 1; i <= n; i++) {
		string temp = arr[i - 1];
		if (arr[i] == temp) continue;
		else cout << arr[i] << '\n';
	}
}

1. 문자열의 길이를 기준으로 대소관계를 판별한다 

2. 만약 길이가 같다면 사전식으로 대소관계를 판별한다. 

 

그래서 비교함수 comp를 보면 문자열의 "길이"를 기준으로 판별하고 싶기때문에 if문에 size가 들어가있는 걸 볼 수 있다. i, j나 둘의 실제 대소관계 그런 걸 따질 필요 없다 우리는 그저 '기준'만 만들어주면 된다. 

 

 

Stable Sort

sort랑 똑같다 

• 단지 차이점은 stable sort는 둘이 같다면 들어온 순서, 즉 배열의 순서에 맞춰 정렬을 해준다.

 

예를 들어 , 백준 10814번 (www.acmicpc.net/problem/10814) 를 보면 

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

vector <pair<int, string>> arr;
int n;
bool comp(pair<int, string> i, pair<int, string> j) {
	 return i.first < j.first;
}

int main() {
	scanf("%d", &n);
	arr.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	stable_sort(arr.begin(), arr.end(), comp);
	for (int i = 0; i < n; i++) {
		cout << arr[i].first <<" "<< arr[i].second << '\n';
	}
}

1. 나이순으로 정렬한다. 

2. 만약 나이가 같다면 인덱스 번호대로 정렬한다. 

 

그냥 sort를 사용했더라면 인덱스도 저장하는 이중 pair 벡터를 만들어서 

사용자 정의 함수에서 나이가 같다면 인덱스 번호 순으로 나열한다고 조건문을 줬어야할 것이다. 

 

하지만 stable sort를 사용하면 같은 요소에 대해 인덱스 순으로 정렬하는 성질 때문에 조건문을 따로 쓰지 않고 깔끔하게 표현 할 수 있다. 

 

 

 

www.cplusplus.com/reference/algorithm/sort/

sort - C++ Reference