[effective STL] 항목 31 : 정렬시 선택 사항들을 제대로 파악

정리

- vector, string, deque, c++ array에 대해 전체 정렬을 수행할 필요가 있을 때는 sort나 stable_sort를 사용한다.

- 상위 n개의 요소만 순서에 맞추려면 partial_sort를 사용한다.

- 상위 n개의 요소를 뽑되 순서를 고려할 필요가 없다면 nth_element가 적합하다.

- 표준 시퀀스 컨테이너가 있고, 이 컨테이너의 요소들을 어떤 기준에 만족하는 것들과

그렇지 않은 것들을 모아 구분하고 싶다면 partition이나 stable_partition을 고려해본다.

- 사용하고 있는 데이터가 list인 경우엔 partition과 stable_partiton은 직접 사용할 수 있으며

sort와 stable_sort 알고리즘 대신에 list:sort 멤버 함수를 사용할 수 있다.

- 만일 partial_sort나 nth_element의 기능이 필요하다면 간접적으로 사용하는 방법이 있지만 상황에 따라 적절하게 구현해야된다.

성능

성능은? 항상 고려해야하는 문제.

partition > stable_partition > nth_element > partial_sort > sort > stable_sort