C++ STL sort() 정리(2차원배열 정렬, 오름차순 정렬, 내림차순 정렬)

 

 

 

 

C++ STL sort() 총정리

 

 

오늘은 C++ STL의 <algorithm> 헤더가 속한 sort() 함수에 대해 정리해 보겠습니다.

2차원배열에서의 정렬, 오름차순, 내림차순등에 대하여 설명하겠습니다.

sort() 함수는 정렬을 해주는 함수로 간편하고 빠르기에 매우 많이 사용되며

단순 정렬문제부터 그리디 알고리즘등 광범위하게 활용되기 때문에

필히 익혀야 합니다.

 

일단 <algorithm> 라이브러리를 추가합니다.

 

 

이제 사용을 해봅시다.

 

 

 

 

사용

 

sort( 시작 주소, 마지막 주소+1, 정렬기준(생략가능) )

 

위처럼 사용하면 됩니다. 정렬기준은 생략 가능하며 기본값은 오름차순입니다.

정렬기준은 조금 있다가 아래에서 다루겠습니다.

예를 들어 int a[10]을 오름차순으로 정렬할 경우

sort(a,a+10)

sort(&a[0], &a[10])

이 두 개 모두 가능합니다.

 

아래 예시 코드를 살펴봅시다.

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[5]={3,5,1,4,2};
    sort(a,a+5);
    //sort(&a[0],&a[5]); 이거도 가능
    for(int i=0; i<5; i++)
        cout<<a[i]<<' ';
}

 

 

위 코드 출력값

 

정렬이 잘 된 것을 확인할 수 있습니다.

참고로 int형(정수)이 아닌 char형이나 string형도 정렬이 가능합니다.

 

    char c[5]={'c','b','a','d','e'};
    sort(c,c+5);
    for(int i=0; i<5; i++)
        cout<<c[i]<<' ';  // a,b,c,d,e

 

 

 

단순 array(배열)이 아닌 vector에서도 사용이 가능합니다!

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int> a;
    a.push_back(5);
    a.push_back(3);
    a.push_back(1);
    a.push_back(4);
    a.push_back(2);
    sort(a.begin(),a.end()); // 이렇게 사용!
    for(int i=0; i<(int)a.size(); i++)
        cout<<a[i]<<' ';
}

vector 사용 예시

 

 

 

 

 

2차원 배열(vector)에서 사용

 

2차원 배열을 정렬할 때 여기서 2차원 배열이란 보통

2열짜리 배열을 말합니다.

즉 a[n][2] 같은 형태를 말합니다.

이러한 형태를 쓰는 이유는

바로 좌표저장을 위해서입니다.

 

2차원 배열을 정렬할 때에는 vector를 사용합니다.

일반 배열로는 sort를 사용할 수 없습니다.

한번 array사용 시 어떻게 되는지 확인해 봅시다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[5][2]={{1,3},{1,2},{1,1},{4,6},{2,4}};
    sort(&a[0][0],&a[4][2]);
    for(int i=0; i<5; i++)
        cout<<a[i][0]<<' '<<a[i][1]<<'\n';
}

 

무언가가 잘못되었다.

 

정렬이 된 것처럼 보이지만

우리가 원하는 것은 이런 것이 아닙니다.

배열의 첫 번째 열을 기준으로 오름차순 정렬 후

값이 같다면 두 번째 열을 기준으로 오름차순 정렬해야 하는데

위에서는 1차원배열을 정렬하듯이 정렬되어 있습니다.

 

 

 

그래서 vector를 사용해야 합니다.

vector만 사용해서는 안되고 pair까지 이용해야 합니다.

pair에 대해서 알아야 합니다.

pair에 대한 설명은 이곳에 자세하게 정리되어 있습니다.

 

C++ STL pair 클래스 정리(vector, sort,백준,응용) (tistory.com)

C++ STL pair 클래스 정리(vector, sort,백준,응용)

 

아래는 예시 코드입니다.

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
int main()
{
    vector<pair<int,int>> p;
    p.push_back(make_pair(1,3));
    p.push_back(make_pair(1,2));
    p.push_back(make_pair(1,1));
    p.push_back(make_pair(4,6));
    p.push_back(make_pair(2,4));
    sort(p.begin(), p.end());
    for(int i=0; i<(int)p.size(); i++)
    {
        cout<<p[i].first<<' '<<p[i].second<<'\n';
    }
}

 

위와 같은 방법을 통해 정렬을 합니다.

pair를 이용하여 sort 하면

별다른 정렬 기준이 없다면

first 값을 기준으로 오름차순 정렬 뒤

값이 같다면 second 값을 기준으로 오름차순 정렬됩니다.

정렬 완료

 

정렬이 잘되었습니다.

 

 

 

오름차순, 내림차순 정렬하기

 

이는 매우 간단합니다.

sort 함수의 형태는 아래와 같다고 했습니다.

sort( 시작 주소, 마지막 주소+1, 정렬기준(생략가능) )

여기서 정렬기준을 바꿔주면 됩니다.

오름차순은 기본값이니 정렬기준을 생략해 주어도 실행되며,

내림차순이라면 정렬기준에 greater<자료형>()을추가하면 됩니다.

 

예를 들어 vector<int> p를 내림차순 정렬하려면

sort( p.begin() , p.end() , greater<int>())를 사용하면 됩니다.

 

만약 pair를 이용한 2차원 배열을 내림차순 정렬한다면?

sort( p.begin() , p.end() , greater<pair<int,int>>())를 사용하면 됩니다.

아래는 예시입니다.

 

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
int main()
{
    vector<pair<int,int>> p;
    p.push_back(make_pair(1,3));
    p.push_back(make_pair(1,2));
    p.push_back(make_pair(1,1));
    p.push_back(make_pair(4,6));
    p.push_back(make_pair(2,4));
    sort(p.begin(), p.end(),greater<pair<int,int>>());
    for(int i=0; i<(int)p.size(); i++)
    {
        cout<<p[i].first<<' '<<p[i].second<<'\n';
    }
}

 

출력 값

내림차순으로 정렬되었습니다.

 

 

 

임의 정렬 기준 만들기

오름차순, 내림차순 외에 임의 기준을 만들어 정렬할 수 있습니다.

일단 2차원 배열에서의 임의 기준은 위에서 설명한 pair글에 

자세하게 설명되어 있고 이 글에서는 1차원 배열에서의 정렬 기준을 설명하겠습니다.

sort() 함수에서 정렬 기준에 들어갈 함수를 만들어 주면 됩니다.

 

먼저 예시를 보이겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b)
{
    return a<b;
}
int main()
{
    int a[5]={3,4,1,2,5};
    sort(a,a+5,cmp);
    for(int i=0; i<5; i++)
    {
        cout<<a[i]<<' ';
    }
}

이 코드의 출력 값은 아래와 같습니다.

 

 

코드를 살펴보면 sort의 정렬 기준은 cmp입니다.

cmp함수의 return 값은 bool값으로 설정해야 합니다.(true, false값 전달을 위해)

함수의 인자로 int a, int b가 설정되어 있는데 이는 정렬 시 값 비교를 위한 인자입니다.

return a<b라고 돼있는데 이는 'a<b가 되도록 정렬하라'라는 의미입니다.

함수에서 인자가 선언된 순서를 보면 a먼저, 그리고 b인데

a<b가 되도록 정렬하면

오름차순으로 정렬이 됩니다.

 

return a>b 이렇게라면 내림차순으로 정렬이 됩니다.

cmp함수의 return을 적절히 조절하여 임의 정렬 기준을 만들 수 있습니다.

 

 

 

sort함수는 코딩테스트, 백준 알고리즘 풀이등에서 유용하게 사용됩니다.

필수입니다. sort함수를 이용하면 빠르고 쉽게 정렬이 가능해집니다.

sort가 좋긴 하지만 쓰기 전에 한번 정렬을 직접 구현해 봅시다.

내가 쓰는 것이 무엇인지 알고 쓰는 것과 모르고 쓰는 것은 천지차이입니다.

 

 

아래에서 sort함수를 이용할 수 있는 문제들을 알려드리겠습니다.

 

백준 2751 : 수 정렬하기 2(실버 5)

백준 1181 : 단어 정렬(실버 5)

 

 

이상 C++ stl의 <algorithm> 라이브러리에 존재하는 sort함수에 대하여 알아보았습니다.

sort