[c++] sort의 종류

들어가며

백준 10814번의 문제를 보며 이전 유형들과 같이 sort에 comp를 지정해서 정렬을 하였고 출력은 정상적이였지만 계속 틀림이 나와서 답을 확인해보니 문제에는 "먼저 가입한 사람"이라는 추가적인 조건값이 있어 stable_sort를 사용해야한다고 했다.

그렇게 공식 문서를 확인해보니 여러개의 sort가 있는 것 같아서 오늘은 sort의 종류를 정리하려고 한다.

 

sort (정렬)

• sort(a, a+n, cmp)
• 우리가 가장 많이 쓰는 단순한 정렬. 기본적으로는 인자의 범위에서 오름차순을 정렬합니다.
• 3번째 함수 인자인 comp를 받아서 요소를 비교하여 원하는 조건에 맞게 정렬합니다.

 

stable_sort (안정적 정렬)

• stable_sort(a, a+n, cmp)
• 안정적 정렬 - 같은 요소이지만 정렬이 일어나도 상대적으로 순서를 유지해줍니다.
• sort와 다르게 정수 부분만의 정렬이 가능합니다.

 

partial_sort (부분 정렬)

• partial_sort(a, a+x, cmp)
• 부분정인 정렬을 수행한다. 위의 예시를 보면  a부터 a+x까지만 정렬하고 이후에는 정렬되지 않은 값이 온다.

 

이후 문제 부분의 sort를 stable_sort로 변경해주어서 맞췄다.

//sort(v.begin(), v.end(), cmp);
stable_sort(v.begin(), v.end(), cmp);