[ C++ ] STL sort 와 stable_sort 함수 설명 및 예제 코드

C++ STL sort 와 stable_sort 함수 설명 및 예제 코드.

안녕하세요.

이번 글에서는 C++의 표준 라이브러리에서 가장 많이 사용되는 함수 중 하나인 "sort"에 대한 내용을 간단한 설명과 예시 코드를 이용해 작성해보려고 합니다.

• C++ 알고리즘: sort - 배열.
• C++ 알고리즘: sort - 벡터.
• C++ 알고리즘: stable_sort

C++ 알고리즘: sort - 배열.

c++에서 "sort" 함수는 표준 라이브러리의 정렬 알고리즘 중 하나로, 퀵 소트를 기반으로 하고 있습니다.

[프로그래밍/알고리즘] - 정렬 알고리즘 - 퀵 정렬 [Quick Sort]

정렬 알고리즘 - 퀵 정렬 [Quick Sort]

아래와 같은 형태로 사용하며, 평균적으로 O(n log n)의 시간복잡도를 가집니다.

또한, 불안정 정렬 알고리즘으로 정렬 후 원본 배열의 순서를 보장하지 않습니다. <--이 부분은 아래 작성할 stable_sort부분을 보면 이해가 가실 겁니다.

*사용하기 위해서 <algorithm>헤더파일을 import 해야 합니다.

#include<algorithm>
sort(startIterator, endIterator, compareFunction);

오름차순- 배열.

오름차순으로 정렬 하기 위해서는 sort(start, end) 를 사용합니다.

"start"와 "end"는 각각 정렬하고자 하는 부분의 시작과 끝을 나타냅니다.

따라서, "sort(arr, arr+n)"과 같이 사용하면 배열 "arr"의 시작부터 'n'개의 원소를 오름차순으로 정렬할 수 있습니다.

*배열은 크기가 고정되어 있기 때문에 크기를 계산해서 사용함.

//오름차순 예제.
#include <iostream>
#include <algorithm> // sort 함수가 선언된 헤더 파일
using namespace std;
int main() {
    int arr[] = {3, 5, 1, 2, 4}; // 정렬할 배열
    sort(arr, arr + 5); // 배열 정렬
    // 정렬된 배열 출력
    for (int i = 0; i < 5; i++) 
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}
//1 2 3 4 5

내림차순-배열.

compareFunction부분에 greater<형식>()을 추가하여 내림차순으로 정렬할 수 있습니다.

#include <iostream>
#include <algorithm> // sort 함수가 선언된 헤더 파일
using namespace std;
int main() {
    int arr[] = {3, 5, 1, 2, 4}; // 정렬할 배열
    sort(arr, arr + 5, greater<int>()); // 배열 정렬
    // 정렬된 배열 출력
    for (int i = 0; i < 5; i++) 
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}
//// 5 4 3 2 1 출력

Compare 함수.

compare 함수를 만들어서 위의 greater sort의 세 번째 인자로 전달하면, 특정 기준에 따라 정렬할 수 있습니다.

이 부분은 아래의 sort-vector에서 이어서 작성하겠습니다.

C++ 알고리즘 : sort - vector

크기가 고정되어 있고, 크기를 변경할 수 없는 array와 다르게 vector는 동적으로 크기를 조절 할 수 있기 때문에 벡터를 정렬하기 위해서는 크기 지정이 필요하지 않습니다.

그 부분을 제외하고는 배열과 사용 방법이 거의 비슷합니다.

아래는 백터 정렬의 예제 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    // 벡터로 정렬
    vector<int> v = {5, 2, 8, 1, 9};
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}
//1 2 5 8 9

이제 위에서 작성하다 말았던 compare 함수에 대해 더 이야기하도록 하겠습니다.

아래 코드는 Person 객체를 age 멤버 변수를 기준으로 오름차순으로 정렬하는 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Person {
    string name;
    int age;
};
bool compare(Person p1, Person p2) {
    return p1.age < p2.age;
}
int main() {
    vector<Person> people {
        {"John", 28},
        {"Jane", 35},
        {"Tom", 21},
        {"Alice", 40}
    };
    sort(people.begin(), people.end(), compare);
    for (auto person : people) {
        cout << person.name << " " << person.age << endl;
    }
    return 0;
}

위 예제에서 age를 기준으로 오름차순으로 정렬하기 때문에, compare 함수에서는 p1.age가 p2.age보다 작을 때 true를 반환하도록 구현하였습니다. 

이런 식으로 custom compare 함수를 사용하면 자료형의 멤버 변수나 일반적인 변수에 따라 정렬할 수 있으며, 다양한 정렬 기준에 맞게 정렬할 수 있습니다.

아래 링크에 나온 문제처럼 custom compare 함수를 사용할 수 있습니다.

https://lazykarr.tistory.com/100

백준 2910 빈도 정렬 C++

C++ 알고리즘: stable_sort()

stable_sort는 안정 정렬 알고리즘으로, 정렬 후 같은 값이 있을 경우 원래의 순서를 유지하는 특징이 있습니다.

일반적으로 O(n long n)의 시간 복잡도를 가지지만, 최악에서는 O(n long^2 n)의 시간 복잡도를 가질 수 있습니다.

또한, stable_sort는 merge sort알고리즘을 사용하므로, 정렬이 된 부분 리스트를 병합할 때, 추가적인 메모리를 사용하게 됩니다. 따라서, 큰 데이터셋에서 사용될 때에는 메모리 사용량에 대한 고려가 필요합니다.

[프로그래밍/알고리즘] - merge sort (합병 정렬)

merge sort (합병 정렬)

아래 코드는 stable_sort의 특징을 보여주는 간단한 코드입니다.

나이와 이름으로 구성된 구조체를 벡터에 담아 custom compare를 사용해 나이를 기준으로 오름차순으로 정렬하고, 나이가 같을 경우 들어온 순서대로 출력하는 stable_sort 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Person {
    string name;
    int age;
};
bool compare(Person p1, Person p2) {
    return p1.age < p2.age;
}
int main() {
    vector<Person> people {
        {"John", 28},
        {"Jane", 35},
        {"Tom", 21},
        {"Alice", 28},
        {"Bob", 21}
    };
    stable_sort(people.begin(), people.end(), compare);
    for (auto person : people) {
        cout << person.name << " " << person.age << endl;
    }
    return 0;
}

결과는 이렇습니다. Tom->Bob, John->Alice인 것을 확인할 수 있습니다.

Tom 21
Bob 21
John 28
Alice 28
Jane 35

추가로 stable_sort는 C++11부터 지원되는 함수로, C++표준 라이브러리의 <algorithm>헤더 파일에 정의되어 있습니다.

마지막으로 stable_sort를 사용해 푼 문제 예시입니다.

https://lazykarr.tistory.com/95

백준 10814 나이순 정렬.