[sort] 정렬

목적

자료구조 속에 들어있는 모든 원소들을 원하는 조건에 맞추어서 정렬한다.

주의점

2개의, 혹은 3개의 argument를 필요로 하는데, 첫번째 두개의 argument는 iterator로써 정렬하는 범위를 나타냅니다. 이때 iterator는 random access와, 수정이 가능해야 합니다.

• stack : iterator를 생성할 수 없을 뿐만 아니라, random access도 수정도 불가능합니다. 따라서 Sort를 사용할 수 없습니다.
• queue : queue를 직접적으로 sort의 첫 번째 두 번쨰 원소로 넣어서는 사용할 수 없습니다.
• deque : 역시 queue와 같은 이유로 안됩니다.
• vector : 역시 sort는 아래의 형태입니다.

std::sort(v.begin(), v.end());

3번째 인자, 비교 함수

y축 값이 작은 순서대로, y축 값이 같다면 x축 값이 작은 순서대로 출력

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

vector<pair<int, int> > gem;
//y축 값이 작은 순서대로, y축 값이 같다면 x축 값이 작은 순서대로 출력
bool bigger(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second != b.second) return a.second < b.second;
	return a.first < b.first;
}

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

	sort(gem.begin(), gem.end(), bigger);
	
	for (int k = 0; k < n; k++) {
		cout << "(" << gem[k].first << "," << gem[k].second << ")" << endl;
	}
	return 0;
}

y축 값이 작은 순서대로, y축 값이 같다면 x축 값이 큰 순서대로 출력

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

vector<pair<int, int> > gem;
//y축 값이 작은 순서대로, y축 값이 같다면 x축 값이 **큰** 순서대로 출력
bool bigger(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second != b.second) return a.second < b.second;
	return a.first > b.first;
}

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

	sort(gem.begin(), gem.end());
	
	for (int k = 0; k < n; k++) {
		cout << "(" << gem[k].first << "," << gem[k].second << ")" << endl;
	}
	return 0;
}

정렬의 방향을 기억하기 쉬운 방법이 있습니다.

bool bigger(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second != b.second) return a.second < b.second;
	return a.first > b.first;
}

second에 대해서는 등호가 <이므로 1<2<3<4<5 오름차순으로 정렬되고,
first에 대해서는 등호가 >이므로 5>4>3>2>1> 내림차순으로 정렬됩니다.

string 길이 기준으로 비교

bool compare(string a, string b) {
    if (a.length() < b.length())
        return true; //여기
    else if (a.length() == b.length())
        if (a < b) return true;
    return false;
}

a와 b의 길이를 비교한 뒤 true가 아닌 return a < b 를 하면 a와 b의 첫 문자의 ascii를 비교하는 방식으로 정렬한다.

lower_bound/upper_bound에서의 compare 전달

lower_bound(v.begin(), v.end(), value, compare)와 같이 진행하면 compare를 기준으로 이분탐색을 진행한다. 이분탐색이 정렬된 데이터에 대해서 진행하기 때문에 정렬에 사용된 compare와 같은 비교함수를 전달한다.

std::pair

pair에 대해선 기본적으로 x기준 오름차순, x값이 같다면 y기준 오름차순으로 적용되어 있습니다.

입력 5 2 7 4 1 2 3 3

출력 (1,2) (3,3) (5,2) (7,4)

vector<pair<int, int> > gem;

...

sort(gem.begin(), gem.end());

구조체 비교 연산자

접근제어 default가 public

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

struct paiir {
	int first;
	int second;
	paiir(int x, int y) {
		first = x;
		second = y;
	}
};

bool operator<(const paiir& a, const paiir& b) {
	if (a.first != b.first) return  a.first < b.first;
	else a.second < b.second;
}
vector<paiir> gem;

int main() {
	int n;
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		gem.push_back(paiir(x,y));
	}

	sort(gem.begin(), gem.end());
	
	for (int k = 0; k < n; k++) {
		cout << "(" << gem[k].first << "," << gem[k].second << ")" << endl;
	}
	return 0;
}

클래스 비교 연산자

접근제어 default가 private

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

class paiir {
private :
	int first;
	int second;
public :
	paiir(int x, int y) {
		first = x;
		second = y;
	}

	bool operator<(const paiir& a) {
		if (a.first != this->first) return  a.first < this->first;
		else a.second < this->second;
	}

	int getFirst(void) {
		return first;
	}
	int getSecond(void) {
		return second;
	}
};


vector<paiir> gem;

int main() {
	int n;
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		gem.push_back(paiir(x,y));
	}

	sort(gem.begin(), gem.end());
	
	for (int k = 0; k < n; k++) {
		cout << "(" << gem[k].getFirst() << "," << gem[k].getSecond() << ")" << endl;
	}
	return 0;
}