오늘의 코딩지식. No. 1 (Sort()함수와 임시 객체)

오늘의 코드 3일차 에서 알아본 Sort() 함수의 개념에 대해 정리해 보았다.

---

abstarct

우리는 "오늘의 코드. 3일 (백준/25305번 커트라인)편"에서 Sort() 함수를 다루어 보았다. 굉장히 자주 사용할 만한 함수이고, 생각보다 깊이 파고들면 알 만한 내용도 많았다. 

1. Sort() 함수의 개념 및 구조
2. 심화 내용 (임시객체)

으로 짧게 구성했다. 한번 알아보도록 하자.

---

Subject 1 - Sort() 함수의 개념 및 구조

Sort() 함수는 C++의 표준 라이브러리 (Standard Template Library = STL)로, 'algorithm' 헤더에 포함되어 있다.

 

이 함수의 시간 복잡도는 무려 최악의 상황에도 O(nLogn) 으로, 다른 정렬에 비해 빠른 모습을 보여준다.

최악의 상황에도 O(nLogn) 을 유지한다.

 

그 비결은? Quick Sort와 Heap Sort와 Insertion Sort를 잘 섞는 것에 있다.

 

1.  Quick Sort로 시작하여서 정렬하다가 재귀의 깊이가 일정수준(2Logn)을 넘어가면 Heap Sort를 이용하여 정렬한다.
2. 위의 과정으로 거의 정렬을 마치면, Insertion Sort를 사용하여 완전히 정렬시킨다.
3. 다만 위의 과정에서 쪼개진 리스트의 크기가 16이하 (여러번의 실험을 통해 얻어진 결과라고 한다.) 면 Insertion Sort를 진행한다.

 

리스트의 크기가 충분히 작다면(16이하) Quick Sort 보다 Insertion Sort가 더 빠르기 때문에 애초에 리스트 16이하라면 Insertion Sort만을 사용한다.

 

Sort 함수의 시간 복잡도는 각 경우에 이렇게 된다.

 

즉, 항상 O(n log⁡ n)이다.

 

 

Sort() 함수의 기본적인 용법을 알아보자. 

#include <functional>

int main()
{
    sort( 시작부분, 끝부분, 비교부분 )
}

 

시작부분은 배열이나 벡터 등의 시작부분, 끝부분은 끝을 나타낸다. 여기서 자세히 봐야할 부분은 비교부분.

임의로 콜백 함수를 지정하여 오름차순, 내림차순 등의 옵션을 변경 가능하다.

 

bool comp(int x, int y)
{
    return x < y;
}

int main()
{
    sort( 시작부분, 끝부분, comp )
}

 

이런 방식으로 comp 함수를 지정하여 원래 Sort() 함수의 기본 옵션인 오름차순에서 내림차순으로 변경이 가능하다.

이 자리는 Bool형 함수나 수식을 넣어 줄 수 있다.

 

여기서 더 나아가 "임시 객체"를 이용하여 조금더 간단히 정렬하는 법이 있는데 Subject 2 에서 알아보자.

---

Subject 2 - 임시 객체

임시 객체란 무엇인가.

말그대로 임시로 사용되는 객체, 즉 실행도중에만 잠깐 썼다 마는 객체이다.

 

functional 이라는 헤더에는 greater등의 정보가 포함되어있다.

#include <functional>

int main()
{
    sort( 시작부분, 끝부분, greater<>() )
}

----- greater의 내부----------

template< class T = void > // 타입은 추론됨 (C++ 14 이후)
struct greater;

constexpr bool operator()(const T& lhs, const T& rhs) const 
{
    return lhs > rhs;
}    

(C++14 이후)

 

이런 객체를 소스코드에 직접 선언해주는 방법도 있지만, 우리는 Sort() 함수에서만 사용할 것이다. 그렇기에 위와 같이 greater<>()로 Sort안에서만 사용할 임시 객체를 만들어준다.

 

이전 C++14 이전에서는...

greater<int>()

와 같이 자료형을 명시해주어야 했으나, 이후부터는 Tamplate를 이용한 타입 추론이 가능해지며 필요 없게 되었다.

(파라미터로 들어오는 값의 타입으로 알아서 타입을 추론해준다.)

 

역으로 오름차순을 나타내는 less<>()도 있다.

template< class T = void >
struct less;


constexpr bool operator()(const T& lhs, const T& rhs) const 
{
    return lhs < rhs;
}

 

위의 greater과 비교해서 정확히 부등호 방향만 반대이다. 

이는 Sort() 함수에서는 기본값으로 오름차순으로 적용되어있다.

 

더해서 두개의 배열/벡터 등을 비교하여 같으면 1, 아니면 0을 출력하는 객체인 equal_to<>() 도 있다.

template< class T = void >
struct equal_to;

constexpr bool operator()(const T& lhs, const T& rhs) const 
{
    return lhs == rhs;
}

---

Conclusion

Sort() 함수 하나만 해도 생각보다 많은 내용이 담겨있다. 여러가지 정렬방법을 사용하여 시간복잡도를 줄인 것을 보면 우리보다 선배 개발자들이 심혈을 기울여 만든 함수들을 우리는 헤더파일 몇개, 몇 글자 타이핑 하면 편리하게 사용할 수 있다는게 신기했다. 어떤 간단한 함수라도 파고들면 수많은 노력의 결정체라는것을 알 수 있다.

존경스럽다.

 

 

혹시 위 정보중에 틀린부분이나 모호한 부분이 있다면 댓글로 알려주길 바란다.

그것이... 댓글이니까...(끄덕)