sort()

배열이나 컨테이너의 요소를 정렬하는 함수이다.

 

보통 array나 vector를 정렬할 때 쓰인다.

O(nlogn)의 시간 복잡도를 가지는 함수이다.

 

sort()에 들어가는 매개변수는 총 3개이다.

2개는 필수이고 한개는 선택이다.

 

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

 

first는 정렬하고 싶은 배열의 첫번째 이터레이터, last는 정렬하고 싶은 배열의 마지막 이터레이터를 넣으면 된다.

 

한마디로 first는 포함하고 last는 포함하지 않는다는 의미이다.

그래서 예를 들어 크기가 5인 a라는 배열 전체를 sort한다고 하면 sort(a, a + 5)라고 써야 한다.

sort 매개변수에는 주소가 들어가니 a[0]이 아닌 a가 들어간다.

 

last 배열에는 마지막요소가 아닌 그 "다음" 위치를 넣어주어야 한다.

 

sort()의 세번째 매개변수, 커스텀 비교 함수를 넣지 않으면 기본적으로 오름차순이다.

커스텀 비교 함수에 greater<타입>()를 넣어 내림차순으로 변경할 수 있다.

참고로 less<타입>()을 통해 오름차순으로 정렬할수 있다.

 

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

using namespace std;

vector<int> vec;

int arr[5];

int main()
{

    // 초기화
    for (int i = 5; i >= 1; --i)
        arr[i - 1] = i;
    
    for (int i = 5; i >= 1; --i)
        vec.push_back(i);
        
    // 오름차순
    sort(arr, arr + 5);
    sort(vec.begin(), vec.end());
    
    for (int i : arr)
        cout << i << ' ';
    
    cout << '\n';
    
    for (int i : vec)
        cout << i << ' ';
    
    cout << '\n';
    
    sort(arr, arr + 5, less<int>());
    sort(vec.begin(), vec.end(), less<int>());
    
    for (int i : arr)
        cout << i << ' ';
    
    cout << '\n';
    
    for (int i : vec)
        cout << i << ' ';
    
    cout << '\n';
    
    // 내림차순
    
    sort(arr, arr + 5, greater<int>());
    sort(vec.begin(), vec.end(), greater<int>());
    
    for (int i : arr)
        cout << i << ' ';
        
    cout << '\n';
    
    for (int i : vec)
        cout << i << ' ';
        
    cout << '\n';
    
    return 0;
}

 

 

우앙 길다..

기본, 오름차순, 내림차순 형태로 다 적어봤다.

 

 

 

잘 되었네~

 

또한 pair를 기반으로 만들어진 vector의 경우 따로 설정하지 않으면, first와 second 순으로 차례차례 오름차순으로 정렬이 된다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> vec;

int main()
{
    for (int i = 10; i >= i; --i)
    {
        vec.push_back({i, 10 - i});
    }
    
    sort(vec.begin(), vec.end());
    
    for (auto it : vec)
        cout << it.first << " : " << it.second << '\n';
        
    return 0;
}

 

 

결과물은 first는 오름차순으로 정렬이 잘 되었지만 second는 내림차순이다.

여기서

for (auto it : v)
    cout << it.first << " : " << it.second << '\n';

이부분에서 정렬이 된것은 그거다.

first 기준으로 정렬이 된것이다.

그래서 원래는 10 : 0, 9 : 1 ... 이런식으로 되어있던 pair vector가 위 결과물처럼 정렬이 된 것이다.

사실 pair기반으로 만들어진 vector의 경우에는 따로 설정하지 않으면 first, second 순으로 차례차례 오름차순으로 정렬이 된다고 하는데, first 기준으로만 된 것 같다 아직 이해를 잘 못했나보다.

음..

 

일단 그렇다면 first는 내림차순, second는 오름차순으로 정렬하고 싶다면 어떻게 해야 할까?

 

커스텀 비교함수를 만들어 매개변수로 넣으면 된다.

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

using namespace std;

vector<pair<int, int>> vec;

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

int main()
{
    for (int i = 10; i >= 1; --i)
        vec.push_back({i, 10 - i});
    
    sort(vec.begin(), vec.end(), cmp);
    
    for (auto it : vec)
        cout << it.first << " : " << it.second << '\n';
        
    return 0;
}

 

sort()를 하면 first가 오름차순으로 정렬되지만 first를 기준으로 내림차순으로 정렬된 것을 확인할 수 가 있다.

 

여기서 sort가 어떻게 동작하는지 알아보자.

 

sort()는 각각의 요소들을 cmp함수가 true가 뜨는 "요소들의 순서"로 바꿔준다.

 

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

using namespace std;

bool cmp(int a, int b)
{
    return a < b;
}

vector<int> vec = {3, 10, 4, 11};

int main()
{
    sort(vec.begin(), vec.end(), cmp);
    
    for (int i : vec)
        cout << i << " ";
}

 

위 코드를 분석해보면 [3, 10, 4, 11]이 있다고 했을 때 10과 4는 a < b가 false이기 때문에 이를 바꿔주어서 4, 10으로 만들고 다른 요소들도 그런지를 확인

 

이러한 과정들을 반복해서 [3, 4, 10, 11]이라는 집합을 만든다.

 

이렇게 해서 모든 요소들이 a < b를 만족하는 집합을 만드는 것이다.

 

어우 길어라