정렬된 범위에 대해 동작하는 알고리즘이 어떤 것들인지 파악해 두자.

특정 알고리즘들은 미리 정렬시킨 범위를 넣어주어야 한다. 만약 이러한 규칙을 지키지 않았을 경우에는 실행시 동작을 예측 할수 없게 된다.

정렬된 데이터를 넘겨야 동작하는 알고리즘

binary_search	lower_bound	upper_bound	equal_range
set_union	set_intersection	set_difference	set_symmetric_difference
merge	inplace_merge
include

binary_search, lower_bound, upper_bound, equal_range 등은 내부적으로 이진 탐색을 사용해서 값을 찾기 때문에 반듯이 정렬된 데이터 범위가 필요하다.
일반적으로 위의 알고리즘들은 로그 시간의 성능을 내준다고 하지만 임의 접근 반복자를 사용할때에만 그렇다. 예를 들어 양방향 반복자등을 사용한다면 한곳에서 다른 곳으로 이동시 인접한 데이타만으로 이동이 가능하므로 선형시간 이상이 걸리게 된다.

set_union, set_intersection, set_difference, set_symmetric_difference 은 set 조작 알고리즘이며 선형시간의 효율을 보인다. 만약 정렬되지 않은 데이타 범위로 동작할 때는 동작자체는 하지만 선형시간을 초과하는 동작시간을 보여준다.

merge, inplace_merge 알고리즘은 merge sort 의 일부분으로 생각할수 있다. 즉 두개의 정렬된 데이타 범위를 합쳐 정렬된 하나의 범위로 만드는 동작이다.

include 는 어떤 범위안에 원하는 값이 들어있는지의 여부를 알아볼때 사용한다. 물론 정렬된 것을 가정하고 동작하므로 정렬되어 있지 않다면 수행시간이 느려지게 된다.

unique 류의 알고리즘은 인접한 동일값에 대해 작용하는 알고리즘으로 정렬되어 있을 경우와 정렬되어 있지 않을 경우 결과가 달라질수 있다. 데이터 범위에서 중복된 값을 모두 제거하고 싶다면 정렬을 한뒤 unique 를 호출해야 하는 것이다.

정렬 기준에 대한 첨언

binary_search, lower_bound, upper_bound, equal_range 등의 알고리즘은 당연히 정렬된 기준과 동일한 기준으로 검색기준을 가져야 정상적으로 작동을 할것이다.

vector<int> v;

…

sort(v.begin(), v.end(), greater<int>());

…

bool a5Exists = binary_search(v.begin(), v.end(), 5);

위의 코드를 볼때 데이터의 범위는 내림차순으로 정렬을 했지만 기본적으로 binary_search는 오름차순을 기준으로 한다. 위의 코드를 정상적으로 작동하게 하기 위해서는

bool a5Exists = binary_search(v.begin(), v.end(), 5, greater<int>());

으로 수정을 해서 binary_search 알고리즘이 내림차순으로 정렬된 데이터 범위라는 것을 알수 있도록 해야 한다.

또한 unique류 를 제외하고 위에서 언급한 정렬된 범위에 대해 동작하는 알고리즘은 두개의 값이 같은지 판정할때 동등성을 기준으로 삼는다.
이와는 반대로 unique류의 알고리즘은 상등성에 의해 두 객체의 같음을 판별하게 된다.(EffectiveSTL19 참조)

정렬 기준에 대한 첨언

댓글 남기기 댓글 취소