C++ STL sort 함수, 비교함수 오버라이딩

std::sort

sort 함수는 <algorithm> 헤더 파일 내에 정의되어 있다. 기본적으로는 (first, last)를 parameter로 받아서 오름차순으로 정렬한다. time complexity는 O(NlogN)이고, 같은 값이 있을 경우 순서는 보장되지 않는다.

 

기본 용례

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main(void) {
    vector<int> a = {5,2,7,3,4};

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

    for(auto i : a) {
        cout<<i<<" ";
    }
}

 

output

2 3 4 5 7
오름차순으로 정렬된 모습을 볼 수 있다.

 

---

 

일반적으로는 오름차순 정렬만 가능하지만, parameter로 compare 함수를 넣으면 다른 순서로 정렬할 수 있다.

 

내림차순 정렬

int main(void) {
    vector a = {5,2,7,3,4};

    sort(a.begin(),a.end(), greater<int>());

    for(auto i : a) {
        cout<<i<<" ";
    }
}

 

output

7 5 4 3 2

comp 파라미터로 greater<int>를 넣었더니 내림차순으로 정렬된 모습을 볼 수 있다.

오름차순으로 정렬하는 원래 상태는 less<int>를 넣어도 같은 결과를 얻을 수 있다.

 

---

 

Parameters

 

parameters	description
first,last	정렬할 범위를 설정한다
policy	사용할 execution policy를 설정한다
comp	비교 함수를 설정한다.

 

비교 함수의 설정

비교 함수는 다음과 같이 정의된다.

bool cmp(const Type1 &a, const Type2 &b);

 

꼭 포인터로 전달받지 않아도 된다.

cmp 함수를 정의함으로써 사용자 정의 자료형을 정렬할 수 있다.

 

using namespace std;

typedef struct person{  
	string name;  
	int height;  
}Person;

bool heightComp(Person a, Person b) {  
	return a.height < b.height;  
}

int main(void) {  
	vector student;

	student.push_back({"철수", 175});
	student.push_back({"영희", 162});
	student.push_back({"영철", 188});
	student.push_back({"민수", 168});

	sort(student.begin(),student.end(), heightComp);
	
	for(auto i : student) {
 	   cout<<i.name<<" ";
	}
}

 

output

영희 민수 철수 영철

 

정리

즉, 첫 번째 인자가 더 작을 때 true가 되는 쪽으로 bool 함수값을 리턴하면 오름차순의 결과를 얻을 수 있다.

 

연산자의 오버라이딩

위와 똑같은 정렬을 연산자를 오버라이딩함으로써 수행할 수 있다.
비교 연산자를 overload해도 된다. 아래 예는 function call operator를 overload한 예이다.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef struct person{  
	string name;  
	int height;  
}Person;

struct {  
	bool operator()(Person a, Person b) {  
		return a.height < b.height;  
	}  
} heightComp2;

int main(void) {  
	vector student;

	student.push_back({"철수", 175});
	student.push_back({"영희", 162});
	student.push_back({"영철", 188});
	student.push_back({"민수", 168});

	sort(student.begin(),student.end(), heightComp2);

	for(auto i : student) {
	    cout<<i.name<<" ";
	}
}

 

output

영희 민수 철수 영철