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

※ 읽으시기 전에

- 제가 현재 숙지하고 있는 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