std::sort를 이용한 정렬

2015. 9. 20. 14:41알고리즘 문제풀기/코딩

algorithm이라는 헤더엔 std::sort() 라는 함수가 있습니다.
#include <algorithm>을 하고 using namespace std;를 하면 sort() 함수를 쓸 수 있습니다.
sort() 함수는 크기가 커지는 순서대로 배열을 정렬하는 함수입니다.
예를 들어 [5, 1, 2, 4]가 있으면 [1, 2, 4, 5]가 되게 정렬하는 식이지요.

a라는 배열의 i번째부터 j번째까지의 값을 정렬하고 싶을 땐 이렇게 씁니다.

sort(a + i, a + j + 1);

이렇게 하면 a[i]부터 a[j]까지(양쪽 경계 포함)의 값이 정렬되어 저장됩니다.
이 함수가 새로운 배열을 반환하는 것이 아니라, a 배열의 값이 바뀌게 됩니다.

  • 첫 번째 인자로는 (범위의 시작점)
  • 두 번째 인자로는 (범위의 끝점 + 1)

을 넣어야 합니다. 두 번째 인자에 +1을 넣는 게 중요합니다.
왜 범위의 오른쪽에만 +1을 하는지 궁금할 수도 있습니다. 이렇게 하면 편한 점이 여럿 있는데, 이 글에서는 다루지 않습니다.

또, 함수의 인자는 배열의 값이 아니라 주소를 써야 합니다.
포인터의 개념을 알고 있다면 포인터를 인자로 넘겨주면 되구요.
아직 포인터를 모른다면 (배열 이름) + (인덱스)를 사용하면 된다고 알고 계시면 됩니다.

int, long long, char처럼 숫자로 비교할 수 있는 변수들은 오름차순 정렬(2, 3, 5, 7, .. 이런 식)이 됩니다.
처음에는 커지는지 작아지는지 헷갈릴 수 있기 때문에 반드시 외우도록 합시다.
오름차순이라는 단어가 익숙치 않다면 1, 2, 3, … 이렇게 외우셔도 좋습니다.

예시 코드를 보여드리겠습니다.

int a[10] = {0, 1, 6, 4, 2, 7, 3, 9, 5, 8};

sort(a + 3, a + 7);
for(int i=0; i<10; ++i) printf("%d ",a[i]);
putchar('\n');
// result: 0 1 6 2 3 4 7 9 5 8
// index   0 1 2[3 4 5 6]7 8 9  <- [3 4 5 6]번째 값이 정렬되었다.

sort(a, a + 10);
for(int i=0; i<10; ++i) printf("%d ",a[i]);
putchar('\n');
// result: 0 1 2 3 4 5 6 7 8 9
// index  [0 1 2 3 4 5 6 7 8 9] <- 전체가 정렬되었다.

같은 값끼리는 서로 붙어 있게 됩니다.

int b[5] = {0, 2, 1, 2, 4};

sort(b, b + 5);
for(int i=0; i<5; ++i) printf("%d ",a[i]);
putchar('\n');
// result: 0 1 2 2 4

이제 다른 정렬에 대해서 알아봅니다.

예를 들어 숫자를 정렬하는 기준을 이렇게 하고 싶을 수도 있습니다.

10으로 나눈 나머지가 0인 것, 1인 것, …, 9인 것이 순서대로 오게 하고 싶다

혹은 이런 기준도 있을 수 있구요.

크기가 작아지는 순서대로 늘어놓고 싶다.

이런 복잡한 경우도 있습니다.

a라는 배열은 따로 있는데, idx라는 배열을 정렬해서, aidx[k]번째 원소가 커지도록 하고 싶다.
예를 들어 a = [6, 2, 9, 5] 이고 idx = [0, 1, 2, 3]이면,
a[1] < a[3] < a[0] < a[2] 이므로 idx = [1, 3, 0, 2]가 되게 하고 싶다.

그리고 이런 중요한 경우도 있습니다.

구조체를 정렬하고 싶다.

그런데 정렬하고 싶은 기준이 두루뭉술한 채로는 컴퓨터에게 정렬을 맡길 수가 없겠죠.
컴퓨터에게는 어떤 식으로 정렬 기준을 전달해야 할까요?

그 기준은, "두 개의 원소를 비교하는 방법"입니다.
즉 두 개의 원소에 대해서 (어느 쪽이 더 앞에 와야 하는가)를 판단하는 방법을 제시하면,
std::sort()가 그 판단 방법을 토대로 배열을 정렬해 줍니다.

그럼 그 '방법'을 어떻게 넘겨주어야 할까요?
"10으로 나눈 나머지를 비교해라" 같은 말을 sort(a, a+5, %10); 같이 전달할 수도 없는데 말이죠.
하지만… 과연 없을까요? 두 값의 정렬 순서를 반환하는 함수를 만드는 걸 생각해 봅니다.

bool 함수이름 (const 변수형& a, const 변수형& b){
    return (a가 b보다 앞에 올 조건);
}

여기서 const나 &는 반드시 넣어야 합니다.
무슨 의미인지 무슨 목적인지를 전혀 모르겠더라도 그냥 외워서 넣으셔야 합니다.
변수 이름은 꼭 a와 b일 필요는 없지만,
첫 번째 인자가 두 번째 인자보다 앞에 올 조건을 반환해야 하는 건 지켜야 합니다.

이제 sort의 세 번째 인자로 이 함수의 이름을 넣으면,
이 함수가 판단한 "a가 b보다 앞에 올 조건"에 따라 구간을 재배열합니다.

예시를 들어볼게요.
앞에서 한 것처럼 10으로 나눈 나머지 기준으로 오름차순 정렬하고 싶다고 합시다.
10으로 나눈 나머지가 (0인 것들...), (1인 것들...), ..., (9인 것들...) 순서가 되겠죠.
그러면 예를 들어 3인 것은 5인 것보다 반드시 앞에 와야 하고,
9인 것은 7인 것보다 반드시 뒤에 와야 하겠죠.
x가 y의 앞에 올 조건은 (x%10)<(y%10) 입니다.
그럼 이렇게 짜면 됩니다.

bool comp (const int& a, const int& b){
    return (a%10) < (b%10);
}

int data[5] = {1, 35, 72, 100, 9};
sort(data,data+5,comp);

이렇게 하면 data 배열의 값은 [100, 1, 72, 35, 9]가 됩니다.
이제는 100이 1보다 먼저 오는 게 재미있지 않나요?
물론 이 상태에서 세 번째 인자 없이 다시 sort(data, data+5);를 실행하면 [1, 9, 35, 72, 100]가 됩니다.
std::sort는 그때그때의 정렬 기준에 따라 정렬합니다.

정렬이 된 상태에서 인접한 값끼리 비교 함수를 호출했을 때 참이 된다고 생각하면 됩니다.
예를 들어 위의 경우에서는 comp(100, 1), comp(1, 72), comp(72, 35), comp(35, 9)가 모두 true인 셈이죠.

같은 기준으로 묶이는 원소(어떻게 정렬하든 상관 없다고 생각할 경우)에 대해서는 false를 반환하면 됩니다.
그 경우에는 위에서 말한 것처럼 꼭 인접한 것들 끼리 comp()의 호출 결과가 true일 필요는 없습니다.

위에 설명한 나머지 경우에 해당하는 비교 함수도 예시를 들어보이겠습니다.

크기가 작아지는 순서대로 늘어놓고 싶다.

bool comp2 (const int& a, const int& b){
    return a > b;
}
int a[5] = {12, 34, 9, 78, 13};
sort(a, a+5, comp2); // a <- {78, 34, 13, 12, 9}가 됩니다.

a라는 배열은 따로 있는데, idx라는 배열을 정렬해서, aidx[k]번째 원소가 커지도록 하고 싶다.
예를 들어 a = [6, 2, 9, 5] 이고 idx = [0, 1, 2, 3]이면,
a[1] < a[3] < a[0] < a[2] 이므로 idx = [1, 3, 0, 2]가 되게 하고 싶다.

int a[4] = {6, 2, 9, 5}, idx[4] = {0, 1, 2, 3};
bool comp3 (const int& i, const int& j){
// 이렇게 변수 이름을 바꾸면 생각하기 더 쉽습니다.
  return a[i] < a[j];
}
sort(idx, idx+4, comp3); // idx <- {1, 3, 0, 2}가 됩니다.

구조체를 정렬하고 싶다.

구조체는 위에서 설명한 int 타입 예시들과 다르게, 대부분 단순 비교가 불가능합니다.
sort() 호출 시 세 번째 인자를 빼면 컴파일 오류가 발생하지요.

struct mypair { int x, y; };
mypair data[10];
bool comp4 (const mypair& a, const mypair& b) {
    return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}
sort(data, data+10, comp4);

연습문제입니다.
이 문제에서 sort()를 어떻게 쓸까 고민해 보세요.
BOJ 1900: 레슬러