[알고리즘] 구조체 정렬 / C++

algorithm 라이브러리 내 sort 함수를 이용한 구조체 정렬 방법에 대해 알아보겠다.

 

자료형 정렬

먼저, 기본적인 자료형의 정렬은 이미 선언되어있는 greater, less 함수를 이용한다.

#include <algorithm>

int arr[5] = { 5,2,4,3,1 };

int main(){
	sort(arr, arr+5, greater<int>());  // 내림차순(큰 것 먼저)
	return 0;
}

// 결과 : arr[5] = { 5,4,3,2,1 }

 

구조체 정렬

구조체를 정렬하기 위해서는 어떤 것을 기준으로 정렬할 것인지 정의하는 함수를 직접 만들어야한다.
나는 주로 함수명을 compare로 선언하고, 인자값을 순서대로 left와 right로 선언해준다.
compare함수의 두 인자값인 왼쪽 값(left) 와  오른쪽 값(right) 를 비교한다.

sort 함수의 세번째 인자에 compare함수를 넣어주면 완성이다.

#include <algorithm>
using namespace std;

struct node {
	int hee;
	char sun;
};

// hee가 오름차순이고, 값이 같을때는 sun 오름차순.
int compare(node left, node right) {
	if (left.hee > right.hee) return 0;
	if (left.hee < right.hee) return 1;
	return left.sun < right.sun;
}

node test[5] = {
	{1, 'z'},
	{3, 'k'},
	{2, 'a'},
	{2, 's'},
	{3, 'b'}
};

int main() {
	sort(test, test + 5, compare);
	return 0;
}

/* 결과
test[5] = {
	{1, 'z'},
	{2, 's'},
	{2, 'a'},
	{3, 'b'},
	{3, 'k'}
}
*/

 

시간복잡도

quick sort 방식이기 때문에 평균 시간복잡도는 O(n*logn)이고, 최악의 경우 O(n^2) 가 될 수도 있다..