stable_sort

stable_sort는 <algorithm>에 정의된 함수로, 주어진 범위의 요소들을 안정적으로 정렬한다. 여기서 안정적이라는 의미는 동일한 키를 가진 요소들의 상대적인 순서가 보존된다는 것이다.

---

⦁ 특징

• 정렬 안정성: 동일한 값의 요소가 정렬 후에도 입력 순서를 유지한다.
• 시간 복잡도:
  • 평균, 최악: $O(N \log^2 N)$
  • sort 함수가 평균적으로 $O(N \log N)$이라서 더 느리지만 안정성을 보장한다.
• 공간 복잡도: 내부적으로 병합 정렬(merge sort) 알고리즘을 사용하기 때문에 $O(N)$의 추가 메모리를 사용한다.

---

⦁ 함수 시그니처

void stable_sort(Iterator first, Iterator last);
void stable_sort(Iterator first, Iterator last, Compare comp);

• first, last: 정렬할 범위를 나타내는 반복자
• comp: 사용자 정의 비교 함수 객체 (선택)

---

⦁ 예시

기본 사용

#include <algorithm>

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1, 2, 4};

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

    for (int num : vec) {
        std::cout << num << " ";
    }
    return 0;
}

출력:

1 2 2 3 4 4 5

사용자 정의 비교 함수 사용

#include <algorithm>

struct Person {
    std::string name;
    int age;
};

// 나이순으로 정렬하되, 같은 나이일 경우 이름순을 유지
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;
}

int main() {
    std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 30}, {"David", 25}};

    // 나이순으로 정렬
    std::stable_sort(people.begin(), people.end(), compareByAge);

    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ")\n";
    }
    return 0;
}

출력:

Bob (25)
David (25)
Alice (30)
Charlie (30)

---

⦁ 사용 시기

동일한 키를 가진 데이터의 순서를 유지해야 하는 경우:

• 예를 들어, 여러 기준으로 데이터를 정렬해야 할 때, 두 번째 기준으로 정렬한 후 첫 번째 기준으로 정렬할 경우 상대적인 순서를 보장하려면 stable_sort가 필요하다.