[Effective STL] 31. 상황별 정렬 선택하기

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

 

 

 

• sort 알고리즘은 정말 좋은 알고리즘이지만.. 늘 최적은 아니다.
• 상황별 정렬 알고리즘을 알아보자.

partial_sort

• 항상 전체 데이터의 정렬이 필요하진 않다.
• 예컨대 vector<Widget>에서 가장 좋은 20개의 Widget만을 골라야 하는 경우라면,
  • 상위 20위까지의 Widget만을 정렬하면 된다.
  • 이럴 때 partial sort를 사용한다.

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
    // lhs의 품질이 rhs의 품질보다 좋으면 true를 반환
}

// 가장 뛰어난 20개의 요소를 앞에서부터 순서대로 정렬
partial_sort(Widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);

 

 

 

nth_element

• 상위 20개가 필요하긴 한데, 순서까지는 필요 없다면 고려할만한 알고리즘이다.
• 자신이 처리할 범위 내의 객체를 정렬하되
  • n번 위치(사용자가 지정한 위치)에 있는 요소만 전체 정렬된 상태에 있게 한다.
• 즉, n번 위치의 정렬만은 확실히 보장되는 알고리즘
  • 위치 n의 앞에 있는 요소들은 n번 위치에 있는 요소보다 정렬 순서에서 뒤에 오지 않는다.
  • 위치 n의 뒤에 있는 요소들은 n째 위치에 있는 요소보다 정렬 순서에서 앞에 오지 않는다.

// 상위 20개 요소를 widget의 앞에 놓는다.
// 단, 20개 요소 각각의 정렬은 보장되지 않는다.
nth_element(widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);

 

 

 

stable_sort

• 동등한 요소들이 여러개 있다면 미묘한 문제가 생길 수 있다.
  
  • 만약 1등 요소가 12개, 2등 요소가 15개 있다면
  • 상위 20개에 들어갈 2등 요소 8개는 어떤 기준으로 골라지게 될까?
• partial_sort와 nth_element는 이 상황에서 '내키는대로' 동작한다.
• 이 상황에서 원래 요소들의 위치를 기준으로 선택하고 싶다면 stable sort를 사용한다.
• 이 종류의 정렬 알고리즘은 두 값이 동등하다면 정렬 후에도 그 둘의 상대적인 위치가 변하지 않는다.
  • 즉, 정렬 되지 않았을 때의 벡터 상대 위치가 보장된다.
  • 요소 A, B가 같은 점수를 가지고, A가 앞에 있었다면, 정렬 후에도 A가 앞에 있다.
• 아쉽게도 partial_sort와 nth_element의 경우 순서 유지성을 가지는 버전이 없다.

 

 

 

nth_element의 다른 용도

• 주어진 범위 내의 중앙값(median)을 찾거나
• 특정한 백분위(percentile) 위치에 있는 값을 찾아낼 때도 사용할 수 있다.

vector<Widget>::iterator begin(widgets.begin());
vector<Widget>::iterator end(widgets.end());

vector<Widget>::iterator goalPostion;

// 정렬된 벡터에서 정중앙 위치에 있는 Widget을 가리킨다.
goalPosition = begin + widgets.size() / 2;
nth_element(begin, goalPosition, end, qualityCompare);

// 원하는 Widget 객체가 widgets의 처음을 기준으로 얼마나 떨어져 있는지 계산한다.
vector<Widget>::size_type goalOffset = 0.25 * widgets.size();
goalPosition = begin + goalOffset; // goalPosition은 75 / 100 위치의 요소를 가리킨다.
nth_element(begin, goalPosition, end, qualityCompare);

• 즉, nth_element는 상위 n개의 요소나 특정 위치 요소를 찾아내기만 해도 될 때 알맞다.

 

 

 

partition

• 상위 20개가 아니라 1, 2등급 Widget 객체만을 골라내야 하는 경우라면?
• 벡터를 정렬해서 3등급의 첫 위치를 찾아도 되겠지만, 쓸데없이 과중한 작업이 될 것이다.
• 이 알고리즘은 범위의 요소 위치를 재배열하는데,
  • 조건에 맞는 요소는 모두 범위의 앞부분에 몰아넣고,
  • 조건에 맞지 않는 요소는 모두 범위의 뒷부분에 몰아넣는다.

bool hasAcceptableQuality(const Widget& w)
{
    // Widget 객체의 등급이 2등급 이상인지 여부 반환
}

// hasAcceptableQuality를 만족하는 모든 Widget 객체는 widgets의 앞으로 몰고,
// 만족하지 않는 Widget 객체 중 처음 것의 반복자를 반환한다.
auto goodEnd = partial(widgets.begin(), widgets.end(), hasAcceptableQuality);

cout << "2등급 이상: ";
for (auto it = widgets.begin(); it != goodEnd; ++it)
	cout << *it << " ";
cout << "\n";

cout << "2등급 이하: ";
for (auto it = goodEnd; it != widgets.end(); ++it)
	cout << *it << " ";
cout << "\n";

• stable 버전도 존재한다.(stable_partition)

 

 

 

정렬 알고리즘 주의점

• 임의 접근 반복자와 함께 사용하므로 vector, string, deque, C++ 배열만 사용 가능하다.
• 표준 연관 컨테이너는 애초에 정렬되는 컨테이너이므로 정렬 알고리즘을 쓸 이유가 없다.
• 하지만 list는 정렬 알고리즘을 사용하지 못한다.
  • 대신 sort 멤버 함수를 제공한다.(stable한 정렬 기능이다.)
  • 즉, partial_sort나 nth_element는 불가능하다.
• 간접적인 list 정렬들
  • 다른 컨테이너에 요소를 옮긴 후 알고리즘을 적용시키기.
  • list::iterator의 컨테이너를 만들어서 알고리즘 적용시킨 후, 해당 컨테이너 반복자로 리스트 요소 데이터 엑세스하기
  • list::iterator의 컨테이너를 만들어서 알고리즘 적용시킨 후,  컨테이너 정보를 써서, 원하는 위치에 리스트의 요소 데이터를 splice하기
• 다만 partition의 경우 양방향 반복자 이상이면 모두 동작 가능하므로
  • STL 표준 시퀀스 컨테이너 모두에 대해 동작한다.

 

 

 

정리

• vector, string, deque, C++ 배열에 대해
  
  • 전체 정렬을 원한다면 sort, stable_sort
  • 상위 n개 요소까지만 정렬을 원한다면 partial_sort
  • 상위 n개 요소를 뽑되, 순서는 필요 없다면 nth_element
• vector, string, deque, C++ 배열, 표준 시퀀스 컨테이너에 대해
  • 특정 기준에 만족하는 것과 그렇지 않은 것을 모아 구분하고 싶다면 partition, stable_partition
• list
  • partition, stable_partition은 직접 사용 가능하다.
  • sort는 멤버 변수로 제공한다.
  • 나머지 기능이 필요하다면 간접적인 방법을 사용해야 한다.
• 알고리즘의 수행 성능 순위
  1. partition
  2. table_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_osrt