[알고리즘] 정렬; C++ STL <algorithm>, 내장함수 sort, compare 함수 만들어 넣기 (백준 2751 좌표 정렬하기)

STL algorithm이란?

c언어를 쉽게 이용할 수 있도록 만든 헤더 파일 중 하나인 algorithm을 이용해 쉽게 정렬을 할 수 있다. 

정렬 - 퀵 정렬, 버블 정렬, 병합 정렬, 선택 정렬

버블 정렬의 시간 복잡도는 O(n^2), 병합 정렬의 시간 복잡도는 O(nlogn) 이다.

병합 정렬에 대해서는 앞선 포스팅 https://chocodingdiary.tistory.com/27 에서 알아본 바 있다.

(물론 1151번 문제는 당시에 해결하지 못했다)

 

STL 헤더 algorithm을 이용하여 sort함수를 호출시키면 쉽게 오름차순으로 정렬을 할 수 있다.

#include <stdio.h>

int main(){
	int arr[10];
    //array 값은 알아서 넣어준다.
    
    sort(arr, arr+10) // array의 시작점과 끝점+1을 적어 sort할 수 있다. 일부분만 정렬도 가능함.
}

stable_sort, std::sort, qsort() 등도 사용할 수 있다,

 

크기가 N인 배열 a에서 

sort(a, a+N) (오름차순 정렬) 또는

sort(a, a+N, compare) 한 뒤, compare함수를 따로 작성하면 원하는 기준에 따라 정렬할 수 있다. 

 

sort함수의 시간 복잡도는 O(nlogn) 이다. 

내림차순으로 쓰고 싶을 때는 compare함수 자리에 greater<int> 를 넣어 쓰기도 한다. 

compare 함수 직접 작성하여 sort()함수 쓰기

bool compare (int i, int j) {
	return a>b
} // a>b일 경우에 1 (true), a<b일 경우에 0 (false) 를 반환하게 된다.

백준 11651: 좌표 정렬하기

좌표이므로 pair 자료형을 이용하였다. pair 자료형을 쓰려면 utility를 사용하고, vector로 선언하여 정렬할 것이므로 vector도 선언해 준다. 

참고: https://withhamit.tistory.com/195

[C++] STL pair를 sort 함수로 내림차순 정렬하기

 

vector를 정렬하기 위해서 bool compare() 함수를 사용하였다.

 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>

using namespace std;

bool compare(pair <int,int> p1, pair <int,int>p2) {
	if (p1.second == p2.second) {
		return p1.first < p2.first;
	}
	else return p1.second < p2. second;
}

int main(){
	vector <pair <int, int> > a;
	
	int n; 
	cin >> n;
	
	int temp = n;
	int t1, t2;
	while (n--){
		cin >> t1 >> t2;
		a.push_back(make_pair(t1, t2));
	}
	
	sort (a.begin(), a.end(), compare);
	int i;
	for(i=0; i<temp; i++){
		cout << a[i].first << " " << a[i].second << "\n";
	}
}

 

bool compare함수 부분만 따로 봤을 때, 

bool compare(pair <int,int> p1, pair <int,int>p2) {
	if (p1.second == p2.second) {
		return p1.first < p2.first;
	}
	else return p1.second < p2. second;
}

pair vector 선언 : vector <pair <int, int> >v로 선언

vector에 요소 집어넣기:v.push_back(make_pair(a,b)); push_back으로 요소 집어넣음 

pair 만들기: make_pair(a,b)

 

bool compare에서 y좌표가 같을 경우 x좌표 오름차순으로, 아닐 경우 y좌표 오름차순으로 정렬하도록 설정하고, sort해준 뒤 각각 요소를 출력하면 끝!