sort 를 이용해 (다중)정렬 하기
C/ C++ 의 algorithm 라이브러리에는 sort 함수를 지원한다. 이 sort 의 시간 복잡도는 O(NlogN)이라고 하는데 이건 또 번외적인 이야기이다. 오늘 할 이야기는 sort 에서 다중정렬 조건을 어떻게 만들어 줄것인가에 대한 이야기이다.
vector 안에 임의의 값을 넣고 정렬을 해보았다.
이렇게 예쁘게 정렬되어 나오는 것을 알 수 있다. 그런데 사실 sort 에는 인자가 하나 더 들어가는데 그것은 compare 즉 비교함수가 들어간다.
사실 내부에 이런 compare 가 작동해서 정렬이 되는 것인데 위 코드를 쉽게 해석하면 n1, n2 즉 두 숫자를 비교해서 더 작을 수록 왼쪽으로 가게 된다. 따라서 vector 가 오름차순으로 정렬되는 것이다. 그러면 내림차순으로 하려면 어떻게 하면될까? 다들 예상이 가겠지만 역으로 작성해주면 된다.
위의 코드와 반대로 compare함수를 작성해주었더니 예상대로 내림차순으로 정렬되었다. 그렇다면 다중정렬은 어떻게 할까? 위에서 작성하던 것과 마찬가지로, 정렬할 조건을 우선순위대로 작성해주면 된다.
예시를 들기 위해 위의 vector 를 살짝 변경해보았다.
예시를 들기 위해 int 와 char 타입의 데이터를 가지고 있는 구조체 Node를 하나 지정해주고 Node 타입의 vector를 만들어서 데이터를 넣어주었다. 우리는 다중정렬을 할 것인데 우선순위는 1. 숫자가 적은 것이 먼저, 2. 알파벳이 작은 순서
로 정렬을 해보고 반대로도 해보려고 한다. 위와 똑같이 compare함수안에 조건을 작성해주면 된다.
위는 숫자, 문자 둘다 오름차순으로 정렬하도록 설정했고, 아래는 둘 다 내림차순으로 정렬되도록 설정했다.
위의 사진에서 보듯이 다중정렬이 잘 되는 것을 확인할 수 있다. 보통 구조체를 이용한 vector,array,priority_queue(heap)등 구조를 이용할때 다중정렬을 해주려면, 꼭 이런 조건을 설정해주기 때문에 한번 알아두면 두고두고 사용할 것이다. 다만 pq의 경우는 사용방법이 약간 다르기 때문에 주의하여야 한다.