[c++/정렬] stable_sort (안정 정렬)

stable_sort

• 동일한 키 값을 가지는 요소들의 입력 순서 유지
  • ex) [3,1,4,1] 에서 첫번째 1과 두번쨰 1의 순서는 정렬 후에도 바뀌지 않음
• 내부적으로 병합 정렬 기반 알고리즘 사용
• 평균 및 최악 시간 복잡도 : 0(N log^2 N)
  • 병합정렬 특성상 비교횟수 많음
• 추가 메모리 많이 사용

 

sort

• 내부적으로 IntroSort 기반 알고리즘
  • 퀵정렬 + 힙정렬 + 삽입정렬 의 조합
• 평균 및 최악 시간 복잡도 : 0(N log N)

 

sort, stable_sort 비교 예제

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

using namespace std;

struct Person {
    int age;
    string name;
};

bool cmp(const Person& a, const Person& b) {
    return a.age < b.age; // 나이 기준 오름차순 정렬
}

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

    // 비안정 정렬
    sort(people.begin(), people.end(), cmp);
    cout << "Using sort:\n";
    for (auto& p : people) {
        cout << p.age << " " << p.name << endl;
    }

    // 안정 정렬
    stable_sort(people.begin(), people.end(), cmp);
    cout << "\nUsing stable_sort:\n";
    for (auto& p : people) {
        cout << p.age << " " << p.name << endl;
    }

    return 0;
}

Using sort:
20 David
25 Charlie
25 Alice
30 Bob

Using stable_sort:
20 David
25 Alice
25 Charlie
30 Bob