C++] vector를 구조체 내 변수 기준으로 정렬하기

 

C++로 알고리즘 문제를 풀거나 이런 저런 이유로 코딩을 하다 보면 vector를 사용하게 되고 이 vector 내에 들어가는 값들을 정렬하기 위해서 직접 정렬을 구현해주는 방법도 있지만 좀 더 최적화되어 빠른 속도로 정렬을 수행해주는 sort함수를 사용하게 된다. 요소의 상대적 위치가 바뀌지 않는 걸 원한다면, stable_sort를 사용하면 된다.

 

통상적으로 자료형이 하나(예를 들어 int 하나)만 들어가는 vector라면, 시작점과 끝만 정해주면 알아서 오름차순 정렬을 수행해버리기 때문에 문제가 되지 않지만, vector 배열에 들어가는 정보가 여러 가지 자료형이 섞여 있는 구조체이고 그 구조체 안의 변수를 기준으로 정렬을 수행해야 한다면, 갑자기 머리가 아파온다.

 

대부분 레퍼런스를 참고하지 않거나 함수를 제대로 사용하는 방법을 몰라서 발생하는 문제인데, 나도 다를 건 없었다.

 

 

나는 크루스칼 알고리즘(Kruskal Algorithm)에서 Edge를 가중치를 기준으로 정렬하려고 하다 보니까 이 문제를 만났다.

 

typedef struct Edge
{
    int vertex1;
    int vertex2;
    int weight;
} Edge;

weight를 기준으로 정렬이 필요한데, 이에 대해 레퍼런스를 뒤져 보면 이런 설명이 있다.

 

https://msdn.microsoft.com/ko-kr/library/mt771443.aspx#sort

 

sort(first, last, comp);

 

comp에 비교 조건을 정의할 사용자 정의 함수를 추가해주면 된다.

애초에 내가 원했던 건 구조체(Edge)의 변수 하나(weight)를 기준으로 오름차순 정렬이 목적이니, 이를 충족시켜줄 정의 함수를 만들어주면 된다.

 

bool CompareWeight(const Edge& x, const Edge& y)
{
    return x.weight < y.weight;
}

 

막상 해보면 별 거 없다.

항상 그 함수를 사용하려고 하면 msdn에 가서 찾아보거나 정의된 부분을 찾아보는 습관을 들이는 게 좋을 것 같다.