gshscs

4. 구조체 정렬

  이 장에서는 구조체를 정렬하는 방법에 대하여 알아보도록 하겠습니다. 일단 구조체 A를 선언하고 sort 함수에 그대로 A를 인자로 전달하면 다음과 같은 컴파일 에러가 발생합니다.

  이항 ‘<’ : ‘A’이 (가) 이 연산자를 정의하지 않거나 미리 정의된 연산자에 허용되는 형식으로의 변환을 정의하지 않습니다.

  사실 몇 가지 에러가 더 발생하지만, 일단 위의 하나만 가져왔습니다. 무엇이 문제인지 대충 감이 잡히실 겁니다. C++에서 기본적으로 제공하는 char, short, int, ... 들은 < 연산이 모두 정의되어있습니다. 하지만 사용자 정의 자료형인 구조체는 < 연산이 기본적으로 정의되어 있지 않습니다.

  예를 들어봅시다. 만약 구조체 A가 다음과 같이 선언되어있고,

struct A {

    int d1,d2,d3;

};

  여기서 A 구조체인 X, Y에 대하여 X<Y 연산을 실행하였다고 합니다. 컴파일러는 d1, d2, d3 원소 중 어느 것을 비교해야 하는지 알 수가 없습니다. 따라서 컴파일 에러를 일으킵니다.

  즉, 구조체 정렬을 위해서는 두 구조체를 비교하는 근거를 제시한 Compare 함수를 인자로 전달하는 과정이 필요합니다. 아래 예시는 EDGE 구조체의 원소 중 w를 오름차순으로 정렬합니다.

--- Source ---

#include<stdio.h>

#include<algorithm>

using namespace std;

struct EDGE {

    int u,v;

    int w;

};

bool cmp_EDGE(EDGE a, EDGE b) { return a.w<b.w; }

int main() {

    EDGE A[]={{1,2,5},{1,4,10},{2,3,7},{3,4,2},{2,4,8},{3,1,1}};

    int size=6;

    sort(A,A+size,cmp_EDGE);

    for(int i=0 ; i<size ; i++)

        printf("u(%d) v(%d) w(%d)\n", A[i].u, A[i].v, A[i].w);

    return 0;

}

--- Output ---

u(3) v(1) w(1)

u(3) v(4) w(2)

u(1) v(2) w(5)

u(2) v(3) w(7)

u(2) v(4) w(8)

u(1) v(4) w(10)

※ 사실 위 소스는 크루스칼 알고리즘에서 간선 가중치를 오름차순으로 정렬하는 소스입니다.

  연산자 오버로딩을 알고 있다면 다른 방법도 가능합니다. 구조체를 정렬할 수 없는 이유는 < 연산자가 정의되어 있지 않다고 앞서 말씀드렸습니다. 다시 말해 < 연산자가 정의되어 있기만 하면 sort 함수가 구조체를 서로 비교할 수 있습니다.

  다음 예시는 바로 앞의 예시를 연산자 오버로딩을 이용하여 정렬을 수행합니다.

--- Source ---

#include<stdio.h>

#include<algorithm>

using namespace std;

struct EDGE {

    int u,v;

    int w;

    bool operator< (EDGE a) { return this->w<a.w; }

};

int main() {

    EDGE A[]={{1,2,5},{1,4,10},{2,3,7},{3,4,2},{2,4,8},{3,1,1}};

    int size=6;

    sort(A,A+size);

    for(int i=0 ; i<size ; i++)

        printf("u(%d) v(%d) w(%d)\n", A[i].u, A[i].v, A[i].w);

    return 0;

}

--- Output ---

u(3) v(1) w(1)

u(3) v(4) w(2)

u(1) v(2) w(5)

u(2) v(3) w(7)

u(2) v(4) w(8)

u(1) v(4) w(10)

  연산자 오버로딩이 객체지향적인 측면에서 조금 더 완성된 스타일이지만, 그렇다고 Compare 함수를 전달하는 방법이 좋지 않은 것은 아닙니다. 각자의 코딩 스타일대로 맞춰 쓰시면 될 듯합니다. (개인적으로는 Compare 함수 전달 방법을 더 많이 씁니다.)

5. stable_sort

  algorithm 헤더 파일에는 [first,last)를 정렬하는 함수로 sort 이외에도 stable_sort, partial_sort 가 있습니다. 이 장에서는 그 중 stable_sort에 대하여 설명하도록 하겠습니다.

  stable? 안정하다? stable_sort라고 했으니 안정한 정렬? 정렬이 안정하다는 것이 도대체 무슨 의미일까요? 다음 정의를 읽어봅시다.

Def) 안정 정렬(stable sort)

  동일한 키 값을 레코드들의 처음 순서가 정렬된 다음에도 그대로 유지되는 정렬.

  다시 말하여 같은 값을 가지는 구간은 정렬을 수행한 후에도 그 구간을 그대로 유지하고 있어야 한다는 이야기입니다.

  예를 들어 컨테이너에 {5,2,3,2,6,2} 가 들어있다고 합시다. 2의 개수가 세 개인데, 이들을 구분하기 위하여 두 번째, 세 번째 2는 !와 @를 붙여 구분하도록 하겠습니다. (!,@는 값과는 무관한 기호입니다.) 즉, 컨테이너에는 {5,2,3,2!,6,2@} 가 들어있는 것인데, 이 컨테이너를 오름차순으로 안정정렬하면 {2,2!,2@,3,5,6} 이 됩니다.

  만약에 stable_sort가 아닌 sort 함수로 위 컨테이너를 정렬하게 되면 어떻게 될까요? 그 때는 정렬의 안정성이 확보되지 않습니다. 따라서 세 개의 2가 어떤 순서로 정렬될지 알 수가 없습니다.

  정렬의 안정성을 확보하기 위하여 stable_sort는 퀵 정렬이 아닌 병합 정렬을 기반으로 합니다. 병합 정렬에서 두 집합을 합칠 때 처음부터 차례대로 원소를 읽어나가는 과정이 정렬의 안정성을 확보하는 근거가 됩니다.

  평균적인 성능으로는 퀵 정렬이 병합 정렬보다는 우수하지만, 최악의 경우에는 병합 정렬이 비교 정렬의 시간복잡도 하한에 더 근접하게 됩니다. (퀵 정렬은 O(n^2), 병합 정렬은 O(nlgn)) 그래서 정렬이 안정하다는 것을 시간복잡도의 변동 폭이 적은 것으로 말하는 분들이 있으신데, 틀린 말은 아니지만 정렬이 안정하다는 것은 같은 값은 순서가 유지된다는 의미로 받아들이는 게 더 적합한 듯 합니다.

  stable_sort 함수 원형은 다음과 같습니다. 사용법은 sort 함수의 사용법과 동일합니다.

template<class RandomAccessIterator>

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

  참고로 하나 더 말씀드리자면, 비교를 기반으로 정렬하는 비교 정렬의 시간 복잡도는 최악의 경우 O(nlgn)을 밑돌 수 없다는 것이 증명되어있습니다. (차후 Math For CS 카테고리에 올릴 예정입니다.) 하지만 입력이 특수한 조건을 만족시키는 경우 이를 극복 가능한 정렬이 있습니다. 기수정렬이 대표적인데, 기수정렬이 위에서 설명한 안정 정렬을 이용하여 O(k) 정렬을 만들어냅니다. (k는 입력 값의 최대 자리 수, 만약 k>n이라면 기수 정렬의 이점이 사라짐.) 물론 안정한 정렬을 위하여 비교 정렬을 사용하지는 않습니다.

※ 읽으시기 전에

- 제가 현재 숙지하고 있는 STL 내용은 대부분 레퍼런스를 참고하지 않고, 직접 이리저리 실험해가며 익힌 내용입니다. 글을 쓸 때는 레퍼런스를 이용하여 검증하지만, 그래도 이론적인 부분에서 제가 틀리게 작성할 수도 있습니다. 따라서 피드백은 언제나 환영입니다.

- 앞으로 소개드릴 자료구조, 함수 등은 반드시 직접 구현할 수 있어야 합니다. 100% 완벽하게 구현할 수 있어도 좋고, 핵심적인 부분만 구현할 수 있어도 좋습니다. 적어도 어떤 원리로 작동하는지는 알아야합니다. 원리를 모른 채 그냥 가져다 쓰는 건 언제 어떤 난관에 부딪칠지 모르기 때문에 상당히 위험합니다. 가져다 쓰는 건 구현이 가능한 이후입니다.

0. qsort 함수와 sort 함수와의 비교

 “qsort 함수가 있는데 sort 함수를 굳이 사용할 필요가 있나요?”

  네, 있습니다. 사실 이 질문은 C++를 아직 제대로 접하지 못하였기에 일어나는 질문입니다. C++ 에서는 여러 가지 자료구조가 내장 라이브러리 내에 선언되어 있습니다. C에서는 아직 이러한 자료구조들이 라이브러리에 포함되어 있지 않기 때문에 qsort 함수는 단순히 배열을 기반으로 설계한 함수입니다. 한편 sort 함수는 연속된 주소 값을 가지는 컨테이너라면 (RandomAccessIterator) 무엇이든 정렬이 가능합니다. 게다가 C++ 에서는 함수의 오버로딩 및 템플릿 화가 되어있어서 인자를 적게 받습니다. 즉, 사용이 용이합니다. 

  그리고 하나 더. sort 함수가 qsort 함수보다 수행 시간이 빠릅니다. 분할이 최악으로 일어날 때 부가적으로 처리하는 부분이 다른 것으로 알고 있습니다. (그런데 우리가 흔히 다루는 범위에서는 많아봐야 50ms 정도 차이나는 정도라 크게 신경 쓰시지 않으셔도 됩니다.)

  마지막으로, 참고용으로 stdlib.h 에 선언되어있는 qsort 함수의 원형을 제시하겠습니다. 바로 다음 장에 제시될 sort 함수의 원형과 비교해 보셨으면 합니다.

qsort(void *_Base, size_t_NumOfElements, size_t_SizeOfElements, int (*_PtFuncCompare)(const void *, const void *))

1. sort 함수의 원형 및 사용법

  sort 함수는 algorithm 헤더 파일의 std 네임스페이스 내부에 선언되어있습니다. 함수의 원형은 다음과 같습니다.

template<class RandomAccessIterator>

void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

  두 번째 선언은 나중에 다시 설명하니 일단 넘어가고. 첫 번째 선언은 [first,last) 범위에 있는 원소를 오름차순으로 정렬합니다. 여기서 [first,last)란 first에 있는 원소는 포함하고, last에 있는 원소는 제외한다는 의미입니다.

  예를 들어 a[0], a[1], ... a[9]를 오름차순으로 정렬하고 싶으면, std::sort(a,a+10); 라 호출하면 됩니다. 전처리기에 using namespace std; 라 적어두면 std::를 생략할 수 있습니다.

ex)

--- Source --- 

#include<stdio.h>

#include<algorithm>

using namespace std;

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size);

    for(int i=0 ; i<size ; i++)

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output --- 

-105 -6 0 3 7 12 27 42 88 903

2. 내림차순 정렬은?

  내림차순 정렬을 위해서는 두 번째 선언을 사용합니다. 두 번째 선언에서 전달받는 인자 중 Compare comp는 비교 함수를 의미합니다. 여기에 functional 헤더 파일에 선언되어있는 greater<자료형>()을 전달하면 내림차순으로 정렬을 수행합니다. 이 비교 함수를 직접 구현하여 인자로 전달하여도 되지만, 여기서는 이미 내장 라이브러리에 선언되어있는 함수를 사용하도록 하겠습니다.

  참고로 less<자료형>()을 전달하면 오름차순으로 정렬을 수행합니다. 이는 첫 번째 선언과 동일한 의미를 가집니다.

ex)

--- Source --- 

#include<stdio.h>

#include<algorithm>

#include<functional>

using namespace std;

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size,greater<int>());

    for(int i=0 ; i<size ; i++)   

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output --- 

903 88 42 27 12 7 3 0 –6 –105

3. Compare 함수 전달

  앞서 내림차순 정렬을 위하여 sort 함수 세 번째 인자로 greater<자료형>()를 전달하였습니다. 여기서는 세 번째 인자로 전달되는 Compare 함수가 어떤 형식을 가지고 있어야 하는 지 설명하겠습니다.

  sort 함수의 인자로 전달되는 Compare 함수는, 정렬하고자 하는 자료형을 두 개 받은 후 정렬이 일어나는 방향으로 true를 반환해야 합니다. 무슨 소리냐고요? 예를 들어 int형 데이터를 오름차순으로 정렬하고 싶다면, int형 데이터를 두 개 받은 후 두 번째 인자가 더 크면 true, 더 작으면 false를 반환해야 한다는 것입니다. (여기서 같은 경우는 true나 false 무엇을 반환해도 상관없습니다.)

  부족한 설명을 대신할 예시를 전달하도록 하겠습니다...^^ 2장 내림차순 정렬 때 greater<자료형>() 대신 직접 Compare 함수를 구현하여 대체하였습니다.

ex)

--- Source ---

#include<stdio.h>

#include<algorithm>

using namespace std;

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

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size,cmp);

    for(int i=0 ; i<size ; i++)

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output ---

903 88 42 27 12 7 3 0 –6 –105