stable_sort

<algorithm> 에 정의됨

template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);  // (1)

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

// 아래 두 함수는 위와 동일하지만 ExecutionPolicy 를 추가로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

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

범위 내의 원소들의 오름 차순 (크기가 작은 것에서 큰 순으로) 안정 정렬을 수행한다 참고로 안정 정렬 이란, 크개가 같은 원소들의 상대적 위치가 바뀌지 않는 정렬이다.

예를 들어서 (3, a), (2, b), (2, c), (1, d) 라는 데이터가 있을 때 정수값으로 안정 정렬을 수행한다면 반드시 (1, d), (2, b), (2, c), (3, a) 가 되지, (1, d), (2, c), (2, b), (3, a) 는 될 수 없다. 왜냐하면 이전에 (2, b) 가 (2, c) 앞에 있었기 때문이다.

(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 을 전달하는 원소의 개수 (N = std::distance(first, last)) 라고 할 때, $O(N (\log N)^2)$ 이다. 만일 추가적인 메모리를 사용할 수 있다면 복잡도는 $O(N\log N)$ 으로 줄어든다.

참고로 함수 내부적으로 정렬해야 할 컨테이너와 같은 크기의 메모리를 처음에 할당하려고 한다. 만일 메모리 할당이 성공 한다면 $O(N\log N)$ 의 속도로 실행이 될 것이고, 실패한다면 조금 느린 버전의 알고리즘이 사용되어 $O(N (\log N)^2)$ 으로 정렬된다.

구현 예시

• libc++

실행 예제

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Employee {
  int age;
  std::string name;  // Does not participate in comparisons
};

bool operator<(const Employee& lhs, const Employee& rhs) {
  return lhs.age < rhs.age;
}

int main() {
  std::vector<Employee> v = {
    {108, "Zaphod"},
    {32, "Arthur"},
    {108, "Ford"},
  };

  std::stable_sort(v.begin(), v.end());

  for (const Employee& e : v) std::cout << e.age << ", " << e.name << '\n';
}

실행 결과

32, Arthur
108, Zaphod
108, Ford

참고 자료

• partial_sort : 범위 안의 첫 N 개의 원소들을 정렬한다.

• sort : 범위 안의 원소들을 오름차순으로 정렬한다.

댓글이 1 개 있습니다!

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

다음으로 로그인

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

댓글 달기

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