c++ sort 함수 커스텀, 특정 조건 정렬, 우선순위 큐 정렬

기본적인 삽입 정렬 및 선택 정렬은 아래 링크를 참조해주세요

2020/10/21 - [알고리즘] - 삽입 정렬 (InsertionSort), 선택 정렬 (Selection Sort) 비교 및 c언어 구현

삽입 정렬 (InsertionSort), 선택 정렬 (Selection Sort) 비교 및 c언어 구현

---

알고리즘 문제를 해결하다보면 algorithm 헤더의 sort 함수를 유용하게 사용합니다.

이 sort 함수를 기존(Default) 정렬 방식이 아닌 주어진 문제에 맞는 정렬 방식을 사용하고 싶다면 sort 의 3번째 파라미터에 정렬 조건에 대한 비교 함수를 넣으면 자신이 원하는 정렬을 수행 가능합니다.

만약, 배열 Arr에 저장된 값들을 짝수보다 홀수에 우선순위를 주고, 오름차순으로 정렬하고 싶다면 아래와 같이 정렬가능합니다.

#include <algorithm>
#include <iostream>
using namespace std;
int arr[10] = { 2,8,4,6,7,5,1,3,10,9 };
int cmp(int a, int b) {
	if (a % 2 && b % 2) { // 둘다 홀수
		return a < b;
	}
	else if (a % 2) { // a만 홀수
		return 1;
	}
	else if (b % 2) { // b만 홀수
		return 0;
	}
	return a < b; // 둘다 짝수
}
int main() {
	cout << "커스텀 sort 실행 전\n";
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";
	sort(arr, arr + 10,cmp);

	cout << "커스텀 sort 실행 후\n";
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << " ";
	}
}

이 외 다양한 정렬 방식을 커스터마이즈하여 사용가능합니다.

또한 우선순위큐와 같은 정렬되는 자료구조에 대해서는 아래와 같이 정렬 옵션을 줄 수 있습니다.

만약 2차원 좌표에 대하여 x축 또는 y축과의 직선거리가 가까운 순서대로 정렬을 해야하는 경우 비멤버 연산자 operator를 사용하여 정렬 가능합니다.

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

struct info {
	int x;
	int y;
};
bool operator <(info a, info b) {
	return min(abs(a.x), abs(a.y)) > min(abs(b.x), abs(b.y));
}
int main() {
	info axis[5] = { {4,5} , {2,3}, {1,9}, {-6, 3}, {5,5} };
	priority_queue<info, vector<info> > pq;
	
	for (int i = 0; i < 5; i++) {
		pq.push(axis[i]);
	}
	cout << "좌표 정렬\n";
	while (!pq.empty()) {
		cout << pq.top().x << ", " << pq.top().y << "\n";
		pq.pop();
	}
}

 이를 응용하면 아래 문제들을 해결 할 수 있습니다.

www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

www.acmicpc.net/problem/11286

11286번: 절댓값 힙