[C++ STL] Header <algorithm> – 1. Sort 파헤치기 (2)

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이라면 기수 정렬의 이점이 사라짐.) 물론 안정한 정렬을 위하여 비교 정렬을 사용하지는 않습니다.