[C++] sort

1. sort()

 

`sort(first, last, *커스텀비교함수)`다.

 

first는 포함되고 last는 포함되지 않는다.

 

시작점 주소와 마지막 주소 + 1을 넣거나 쉽게 iterator.begin()과 iterator.end()를 넣으면 된다.

 

커스텀비교함수는 옵션이다.

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

using namespace std;

//sort(first, last, *커스텀비교함수)
vector<int> a;
int b[5];
int main(){
    for(int i=5; i>=1; i--) b[i-1] =i;
    for(int i=5; i>=1; i--) a.push_back(i);
    //ascending order default
    sort(b, b+5);
    sort(a.begin(), a.end());
    for(int i : b) cout << i << ' ';
    cout << endl;
    for(int i : a) cout << i << ' ';
    cout << endl;

    //ascending order Explicitly
    sort(b, b+5, less<int>());
    sort(a.begin(),a.end(),less<int>());
    for(int i : b) cout << i << ' ';
    cout << endl;
    for(int i : a) cout << i << ' ';
    cout << endl;

    //decending order Explicitly
    sort(b, b+5, greater<int>());
    sort(a.begin(), a.end(), greater<int>());
    for(int i : b) cout << i << ' ';
    cout << endl;
    for(int i : a) cout << i << ' ';
    cout << endl;

    return 0;
}
/*
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
5 4 3 2 1 
5 4 3 2 1 
*/

• sort(b, b+5); ,sort(a.begin(), a.end()); : 배열, 벡터를 오름차순(기본값) 정렬.
• sort(b, b+5, less<int>());, sort(a.begin(),a.end(),less<int>()); : 배열, 벡터를 정렬.
• sort(b, b+5, greater<int>());, sort(a.begin(), a.end(), greater<int>()); : 배열, 벡터를 내림차순 정렬.

 

greater가 내림차순이고 less가 오름차순으로 정렬한다.

• greater : first가 last보다 크다 → 내림차순
• less : first가 last보다 작다 → 오름차순

 

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

using namespace std;

vector<pair<int, int>> v;
int main(){
    for(int i =10; i>= 1; i--){
        v.push_back({i, 10-i});
    }
    sort(v.begin(), v.end());
    for(auto it : v) cout << it.first << " : " << it.second << endl;
    return 0;
}
// default : first, second, third 순으로 차례차례 오름차순
/*
1 : 9
2 : 8
3 : 7
4 : 6
5 : 5
6 : 4
7 : 3
8 : 2
9 : 1
10 : 0
*/

• pair를 기반으로 만들어진 vector는 기본적으로 first, second 순으로 오름차순 정렬됨.

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

using namespace std;

vector<pair<int, int>> v;
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}
int main(){
    for(int i = 10; i >= 1; i--){
        v.push_back({i, 10-i});
    }
    sort(v.begin(), v.end(), cmp);
    for(auto it : v) cout << it.first << " " << it.second << endl;
    return 0;
}
/*
10 0
9 1
8 2
7 3
6 4
5 5
4 6
3 7
2 8
1 9
*/

• sort(v.begin(), v.end(), cmp); : cmp라는 커스텀 비교함수를 사용하는 경우다.
• return a.first > b.first; : a.first가 b.first보다 크다 → greater → 내림차순

 

---

23년 9월 5일 추가

 

나. stable_sort

bool cmp(int a, int b){
    if(cnt[a] == cnt[b]) return seq[a] <= seq[b];
    return cnt[a] > cnt[b];
}

cmp 함수에서 seq를 사용할 때, 같은 빈도수를 가진 값들 사이의 순서를 올바르게 유지하기 위해 seq[a] <= seq[b]로 설정했다.

 

하지만 이러한 방식은 “stable”한 정렬 알고리즘에만 유용합니다.

 

stable이란 정렬 알고리즘의 특성 중 하나로, 같은 값의 원소들 사이의 상대적인 순서가 정렬 전과 정렬 후에 동일하게 유지되는 특성을 의미한다.

 

그러나 std::sort는 기본적으로 stable한 정렬을 보장하지 않는다.

 

만약 stable한 정렬이 필요한 경우에는 std::stable_sort를 사용해야 한다.

 

아래 2910번 예시를 참고하면 좋음.

[알고리즘] 2910번: 빈도 정렬

https://cplusplus.com/reference/algorithm/stable_sort/