C++ STL vector sort 정렬함수

C++에서는 기본적으로 #include <algorithm>을 추가하는 것 만으로도 별도 구현없이 sort함수를 사용할 수 있다.

또한 sort의 인자로는
sort(시작,끝,비교함수); 방식으로 사용이 가능하다.

간단하게 int형 벡터 v를 처음부터 끝까지 오름차순 정렬을 하기 위해선

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

와 같이 코드 한줄로 처리가 가능하다.

---

하지만, vector에 int형만 사용하는 것이 아니라, 다른 type의 변수를 사용해야 하는 경우도 많다.

이런 경우 compare함수를 구현하여 sort함수의 세번 째 인자에 넘겨 줌으로써 두 값을 비교하여 정렬 할 수 있다.

struct person {
   int age;
   std::string name;
};
bool comp(person a, person b) { return a.age > b.age; }
std::vector<person> v;
sort(v.begin(), v.end(), comp);

위의 예제는 struct 또는 class를 사용할 경우, 대소비교를 바로 할 수 없기 때문에 comp함수를 추가하여 age값의 비교를 통해 오름차순 정렬 할 수 있도록 작성한 예시다.

---

만일 위의 예제를 사용할 경우 같은 age인 객체의 경우 순서를 보장해 줄 수 없다.

만일 같은 age인 경우 이름을 기준으로 정렬하고 싶을 경우

bool comp(person a, person b) {
return a.age == b.age? a.name > b.name : a.age > b.age;
}

와 같이 변형하여 age가 같은경우 이름을 기준으로 대소 비교를, 같지 않은 경우 age를 통해 정렬하도록 변형을 할 수 있다.

---

만일, age, name이 모두 동일할 경우 vector에 있던 원래의 순서가 우선시 되어야 할 경우 (age, name외 값이 존재하며, 서로 다름이 구분지어질 경우) sort함수를 사용하면 순서가 어긋난다.

이를 해결하기 위해선 stable_sort를 이용하여, 기존의 순서를 보장받을 수 있다.

---

sort방법은 다양하며, 위에 적힌 예제 외에도 operator > 를 override 하여 compare함수 구현없이 처리할 수 있으며, greater, less 같은 함수를 이용하여 오름차순 / 내림차순이 바로 적용되도록 할 수 있다.