[이론] C의 qsort와 C++의 sort 중 누가 더 빠를까?

---

서  론

우선 이러한 차이점이 존재한다는 것을 알게 해주신 멘토님께 감사의 말씀을 올린다.

 

신입의 가장 큰 적은 알려고 하지 않는 자세보다 (그건 조금 더 근원적인 문제이고…)

무엇을 알아야하는지 모르는 미지성이다, 라는 말이 크게 와닿는 순간이었다.

 

필자는 CS를 접한 이유로,

온갖 것이 다 신기했고 재밌었다.

그야말로 천직이다, 싶을 정도로. (그에 반해 원래 전공인 전기공학에서의 전력시스템이나 전자기학에 관한 것은 놀랍게도 흥미가 없었다……. 그저 학점을 채우기 위해 듣고 외울 뿐…….)

 

그런데 공부를 하다 보면 알게되는 사실이지만,

내가 굳이 알고 싶지 않아서가 아니라, 정말 이러한 차이나 기능이 있는지를 몰라서 모르는 경우가 왕왕 발생한다.

 

이번에 소개할 C언어의 qsort와 C++ sort의 속도 차이 또한 그렇다.필자는 당연히 C언어의 qsort가 더 빠르려니, 했다. (일반적으로 C언어가 C++언어보다 더 빠르다고 생각하니)

 

그러나 당연하게도, 그렇지 않았다.

그렇다면 C언어의 qsort와 C++언어의 sort의 차이점을 알아보자.

---

C qsort() vs C++ sort()

C언어의 Standard C Library는 qsort 함수를 제공한다.

 

void qsort(void* base, size_t num, size_t size,
           int(*comparator)(const void*, const void*)

 

C++언어에서도 비슷하게, STL에서 sort 함수를 제공한다.

 

void sort(T first, T last)

void sort(T first, T last, Compare comp)

 

이때, 동일한 값의 요소(element)는 순서를 보장받지 못한다.

(이는 C++의 std::stable_sort() 함수로 보장받을 수 있다.)

 

이때 C언어의 qsort 함수는 quicksort (퀵 소트) 알고리즘을 이용하며,

C++언어의 sort 함수는 introsort라는 하이브리드 알고리즘을 이용한다.

 

이 C++의 introsort라는 하이브리드 알고리즘은,

introsort만으로도 quicksort와 heap sort의 하이브리드인데,

이 introsort가 진행된 후 insertion sort(삽입정렬)이 연이어서 진행된다.

 

시간복잡도

C의 qsort는 퀵소트이기 때문에 평균 O(n log n), 최악 O(n ^ 2) 이며,C++의 sort는 C++11 기준 최악 O(n log n)을 보장한다.

 

반응형

실제 빠르기 비교

실제로 C의 qsort()와 C++의 sort()를 비교하면,

C++의 sort()가 압도적으로 빠르다.

 

C++의 sort()는 손으로 직접 구현한 퀵 소트보다 20% ~ 50% 가량 더 빠르며,

C의 qsort()보다는 250% ~ 1,000% 더 빠르다.

 

만약 100만 개의 element를 지닌 배열을 정렬할 시,

C의 qsort()는 실행시간 0.247883초,

C++의 sort()는 실행시간 0.086125초가 걸리게 된다.

 

이  유

그렇다면 왜 이렇게 속도 차이가 나는가?

보통이라면 C가 C++보다 빠른 것이 당연하다고 생각했던 필자에겐 큰 충격이었다.

 

우선 C++의 sort()가 C의 qsort()보다 압도적으로 빠른 이유는 두 가지이다.

 

첫 번째,

C++의 sort()는,int 컨테이너의 sort()는 기본적으로 std::less::operator()를 사용하도록 컴파일되며, inline 함수화되고, sort() 함수는 정수를 직접 비교하게 된다.

 

두 번째,

C언어의 qsort()는, 함수 포인터가 매번의 정수 비교마다 간접적으로 호출되며, 이 오버헤드로 인해 현저한 속도 차이를 보이게 된다. 즉, 컴파일러의 최적화 실패 사례이다.

 

심지어 속도 차이뿐만이 아니라, type-safety마저 C언어의 qsort()가 밀린다.

template화된 C++의 sort()는 불안전한 void 포인터로 데이터 항목에 접근할 필요가 없기에 type-safe하지만,

C언어의 qsort()는 void 포인터로 데이터 항목에 접근을 해야만 하기 때문에 type-safe하지 못하다.

 

결  론

요즘에야 파이썬이나 Golang을 주로 사용하기에 C와 C++에서 손을 놓은 지 조금 됐지만,

그래도 임베디드 프로그래밍을 하며 C와 C++ 중 C를 더 많이 사용해왔기에, C에 대한 애착은 남다르다.

 

하지만 이러한 C++ STL의 진화, 그리고 C의 충격적인 속도 차이를 보니 가슴이 아플 뿐이다.

 

그 뿐만 아니라,

이러한 점까지 탐구해볼 필요가 있다는 점에 있어서, 그리고 그러해야한다는 의식조차 없었던 것을 확인했다는 점에 있어서, 필자가 아직 멀었다는 생각이 들게 만들었다.

 

더 많이 공부하고, 더 많이 탐구하고, 더 많이 성장해야겠다는 생각이 들었다.

---