[C++] sort vs stable_sort with C++

sort vs stable_sort

개요

　데이터를 정렬할 때 동일한 값들이 존재하는 경우가 발생할 수 있다. 이때, 우리가 사용하는 일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않아서, 정렬 후의 순서가 원래의 순서와 다를 수 있다. 예를 들어, 이름으로 사람들을 정렬한 후, 나이로 다시 정렬하면 나이가 같은 사람들의 상대적인 순서가 정렬된 후에 변경될 수 있다.

---

본문

출처: cppreference

　C++ 표준 라이브러리에는 정렬 함수로서 std::sort()와 std::stable_sort()가 존재한다. 이 두 함수는 기본적으로 배열 또는 벡터의 시작과 끝 위치를 인자로 받으며, 선택적으로 비교 함수를 추가하여 사용할 수 있다. 둘 모두 시간 복잡도는 평균적으로 O(n log n)으로, 대략적으로 n log n 번의 비교를 수행한다. 하지만 std::stable_sort()는 동일한 값들 사이의 상대적인 순서를 유지하는 추가적인 작업이 필요하므로, 실제 실행 시간은 std::sort()보다 약간 더 길게 나올 수 있다.

　따라서 이 두 함수는 각각의 적절한 상황에서 사용해야 한다. 특히, 동일한 값들 사이의 상대적인 순서를 유지해야 하는 상황에서는 std::stable_sort()를 사용하는 것이 바람직하다. 예를 들어, 우리가 이름으로 사람들을 정렬한 후, 나이로 다시 정렬하려고 할 때, std::sort()를 사용하면 나이가 같은 사람들의 원래 이름 순서가 보존되지 않을 수 있다. 이럴 때 std::stable_sort()를 사용하면 원래의 순서를 보존한 채로 새로운 기준에 따라 정렬할 수 있다.

　반면에, 동일한 값들 사이의 상대적인 순서가 중요하지 않거나, 더 빠른 실행 시간을 원하는 경우에는 std::sort()를 사용하는 것이 효율적일 수 있다. 이는 std::sort()가 동일한 값들 사이의 상대적인 순서를 보존하지 않아도 되는 데 따른 추가적인 연산이 필요 없기 때문에, 동일한 데이터에 대해 보통 std::stable_sort() 보다 더 빠르게 실행될 수 있다.

　요약하자면, 안정적인 정렬이 필요한 경우와 그렇지 않은 경우를 명확히 구분하고, 각 상황에 맞는 적절한 정렬 함수를 선택하여 사용하는 것이 중요하다. 이렇게 함으로써 더 효율적인 프로그래밍이 가능해진다.

---

예제

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

struct Student 
{
    int id;
    int score;
};

bool compare(const Student& s1, const Student& s2) 
{
    return s1.score < s2.score;
}

int main() 
{
    std::vector<Student> students = 
    {
        {1, 90},
        {2, 90},
        {3, 80},
    };

    std::cout << "unstable sort: ";
    std::sort(students.begin(), students.end(), compare);

    for (const auto& student : students) 
        std::cout << "ID: " << student.id << ", Score: " << student.score << '\n';
    

    std::cout << "stable sort: ";
    std::stable_sort(students.begin(), students.end(), compare);

    for (const auto& student : students)
        std::cout << "ID: " << student.id << ", Score: " << student.score << '\n';

    return 0;
}

출력 결과

 

　이 예제를 통해 우리는 동일한 점수를 가진 학생들의 순서가 std::sort와 std::stable_sort에서 어떻게 처리되는지 볼 수 있다. std::sort는 불안정한 정렬 알고리즘으로, 동일한 점수를 가진 학생들의 ID 순서를 보장하지 않는다. 반면에 std::stable_sort는 동일한 점수를 가진 학생들 사이의 상대적인 순서를 유지한다.

　그러나 중요한 점은, std::sort가 불안정한 정렬이라고 해서 항상 동일한 값들 사이의 순서가 변경된다는 게 아니라는 것이다. 이는 C++ 표준에서 명시되어 있지 않으며, 실제 동작은 구현에 따라 달라질 수 있다. 즉, std::sort에 의한 원소의 상대적인 순서 변경은 가능성에 불과하다는 것이다. 따라서, 상대적인 순서가 중요한 경우에는 안정적인 정렬 알고리즘인 std::stable_sort를 사용하는 것이 좋다.

---

요약

sort vs stable_sort
- 원소 간 순서가 유지되어야 한다면 stable_sort, 그렇지 않다면 sort를 사용