항목 31 : 정렬시의 선택 사항들을 제대로 파악해 놓자.

내가 STL에 조예가 깊어서 글을 남기는 것이 아니라, Effecitve STL 을 공부하는 사람들이 이 글을 보고, 도움이 되었으면 하는 생각과, 혹시 내가 틀린것이 있다면 지적해 주시지 않을까 란 생각으로 글을 올리는것임을 미리 밝힙니다.  - 최익필

이번 항목에서는 정렬을 하고자 할때, 이용되는 sort 라는 함수들의 효율을 정확히 파악해 두어 사용하라는 것이다.

sort 알고리즘은

sort, stable_sort, partial_sort, nth_element, partition가 있고, 어떻게 사용하면 좋은지 정리해보자.

Sequence Container 이거나 배열이라는 조건 하에서
1. 전체 정렬을 할 때, sort 나 stable_sort
2. 상위 n개의 요소만 순서에 맞추어 뽑아내고자 할 때, partial_sort
3. 상위 n개의 요소를 뽑되 순서는 고려될 필요가 없을 때, nth_element
4. 어떤 기준에 맞는것과 안맞는것을 분류하고자 할 때, partition 이나 stable_partition

Associative Container 중 list Container 일 경우
멤버 함수 sort 를 사용하는게 좋고, partial_sort 나 nth_element 의 기능이 필요하다면 간접적으로 구현하는 방법밖에 없다고 필자는 말한다.


프로그래머라면 가장 적은 부하의 정렬 알고리즘 순서는 무엇일까? 생각하게 되는데 그 순서는
1. partition
2. stable_partition
3. nth_element
4. partial_sort
5. sort
6. stable_sort
이다.

그렇다고 이것은 절대적인게 아니다. 효율적으로 어떤 정렬 알고리즘을 사용하느냐에 따라 성능이 바뀔수 있기 때문이다.