C++ 레퍼런스 - std::partial

모두의 코드
C++ 레퍼런스 - std::partial_sort (<algorithm>)

작성일 : 2020-12-06 이 글은 6441 번 읽혔습니다.

이 레퍼런스의 모든 내용은 여기를 기초로 하여 작성하였습니다.

아직 C++ 에 친숙하지 않다면 씹어먹는 C++ 은 어때요?

partial_sort

// 참고로 아래 두 함수는 C++ 20 부터 constexpr 함수
template <class RandomIt>
void partial_sort(RandomIt first, RandomIt middle, RandomIt last);  // (1)

template <class RandomIt, class Compare>
void partial_sort(RandomIt first, RandomIt middle, RandomIt last,
                  Compare comp);  // (2)

// 위 (1), (2) 와 동일하지만 ExecutionPolicy 를 추가적으로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void partial_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt middle,
                  RandomIt last);

template <class ExecutionPolicy, class RandomIt, class Compare>
void partial_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt middle,
                  RandomIt last, Compare comp);

범위 내의 원소들을 재배치 시켜서 first 부터 middle 전 까지 범위 내의 가장 작은 원소들을 오름차순으로 배치한다. 따라서 middle 부터 last 까지에는 first 부터 middle 까지의 원소들 보다 큰 원소들이 자리하게 된다.

크기가 같은 원소들의 상대적 위치는 바뀔 수 있으며, first 부터 middle 전에 들어가지 않는 원소들의 상대적 위치 역시 바뀔 수 있다.

예를 들어서 시험 성적의 하위 100 명만 추려내고 싶다면 partial_sort 를 통해서 first 와 middle 을 딱 100 명만 되게 하면 된다. 이를 통해 sort 를 사용해서 전체 응시자를 정렬하는 것 보다 더 효율적으로 수행할 수 있다.

(1) 번 함수의 경우 operator< 를 사용해서 크기 비교를 수행한다. (2) 번 함수의 경우 비교 함수인 comp 를 이용해서 크기 비교를 수행한다.

밑의 두 함수의 경우 추가적으로 실행 방식을 첫 번째 인자로 전달할 수 있는데, 전달하는 policy 의 경우 반드시 std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 를 만족해야 한다.

인자들

first, last: 정렬할 원소들의 범위를 나타낸다.
policy : 사용할 실행 방식
comp : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

bool cmp(const Type1 &a, const Type2 &b);

이 때 함수의 인자 타입은 반드시 const& 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 Type1 과 Type2 로 치환 가능해야만 한다.

리턴값

없음

시간 복잡도

전체 원소의 개수를 $N$ 이라 하고, first 와 middle 전 까지 원소 개수를 $M$ 이라고 하면, 전체 시간 복잡도는 $N\log M$ 이 된다.

구현 예시

실행 예제

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
  std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

  std::partial_sort(s.begin(), s.begin() + 3, s.end());
  for (int a : s) {
    std::cout << a << " ";
  }
}

실행 결과

0 1 2 7 8 6 5 9 4 3

참고 자료

nth_element : 주어진 원소로 해당 범위내의 원소들을 파티션 한다.
stable_sort : 범위 내의 원소들을 안정 정렬 한다.
sort : 범위 내의 원소들을 오름차순으로 정렬한다.

첫 댓글을 달아주세요!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글을 불러오는 중입니다..

모두의 코드 C++ 레퍼런스 - std::partial_sort (<algorithm>)