[Algorithm] sort() 함수 사용하기(feat. compare 이용하기 )

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많으며 대부분 c++ 라이브러리를 사용하여 정렬을 하는 경우가 많다. 이번엔 sort함수를 간단하게 알아보고 정렬하기 위해 sort의 세번째 인자로 전달해 주는 함수 사용법을 알아보도록 하겠다.

 

sort() 란

먼저 sort()를 사용하기 위해 algorithm 헤더파일을 include 해야한다.

sort 함수는 내부적으로 IntroSort라는 정렬 방법으로 구현되어있다. 이 방법은 QuickSort와 HeapSort와 InsertionSort를 합쳐놓은 방식으로 평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 QuickSort와는 달리, 최악의 경우에도 nlogn을 복잡도를 보장한다.

 

https://en.wikipedia.org/wiki/Introsort

Introsort - Wikipedia

---

sort() 이용해서 정렬하기

 

sort는 기본적으로 오름차순으로 정렬된다. 첫번째는 배열을 사용해서 정렬한 것이고 두번째는 벡터를 사용해 정렬한 것이다. 배열을 이용하여 정렬하고자 할때는 배열의 시작점 주소와 마지막 주소 + 1를 적어야 한다. 

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

using namespace std;

int main(void) {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
	sort(a, a + 10);
	for(int i = 0; i < 10; i++) {
		printf("%d ",a[i])
	}
}

출력 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

 

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

using namespace std;

int main(void) {
	vector <int> v;
	v.push_back(9);
	v.push_back(3);
	v.push_back(5);
	v.push_back(4);
	v.push_back(1);
	v.push_back(10);
	v.push_back(8);
	v.push_back(6);
	v.push_back(7);
	v.push_back(2);

	sort(v.begin(), v.end());
    
	for(int i = 0; i < 10; i++) {
		printf("%d ",v[i])
	}
}

출력 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

아래와 같이 compare() 함수를 만들어서 sort()의 세 번째 인자 값으로 넣게 되면, 해당 함수의 반환 값에 맞게 sort()가 실행된다. 이때 compare함수의 반환값을 어떻게 해야 오름차순이고 내림차순인지 헷갈릴 수 있다. 오른쪽이 왼쪽보다 크기때문에 오른쪽은 계속 크게 정렬될 것이다. 따라서 오름차순으로 정렬된다고 생각하면 외우기 편하다.

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

bool compare(int a, int b) {
	return a < b;
} 

int main(void) {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
	sort(a, a + 10, compare);
	for(int i = 0; i < 10; i++) {
		printf("%d ",a[i]);
	}
}

출력 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

반대로 변수 a와 b를 비교하는 compare() 함수에서 반환 값만 > 으로 바꾸면 내림차순으로 결과가 바뀌는 것을 확인할 수 있다. 즉, 두 개의 데이터를 비교할때, 왼쪽에 있는 것이 더 크도록 정렬하겠다는 뜻이다. 

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

bool compare(int a, int b) {
	return a < b;
} 

int main(void) {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
	sort(a, a + 10, compare);
	for(int i = 0; i < 10; i++) {
		printf("%d ",a[i]);
	}
}

출력 : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1