C qsort 함수 vs C++ sort 함수 (작성중)

참고자료: 

https://www.geeksforgeeks.org/c-qsort-vs-c-sort/

http://gshscs.tistory.com/11

알고리즘을 공부하면서 qsort와 sort 함수의 성능 차이가 궁금해져서 찾아보았다.

그래서 위 링크의 글 정리해봄

1. qsort와 sort 함수?

(1) qsort

qsort는 본래 C언어의 함수이다.

C에서는 <stdlib.h>에 정의되어 있으며, C++에서는 <cstdlib>헤더를 포함하여 사용할 수 있다.

(2) sort

sort는 C++함수로 <algorithm>헤더를 포함하여 사용할 수 있다.

2. 구현

(1) qsort

퀵소트(QuickSort) 알고리즘을 통해 구현되었다.

(2) sort

sort함수는 구현마다 사용된 알고리즘이 각각 다르다.

3. 복잡성(Complexity)

(1) qsort

C 표준 라이브러리는 qsort의 복잡성에 대해 논하지 않는다고 한다.

복잡성에 대한 보장을 하지 않는다는 뜻 같다(아마도...?).

(관련 링크: https://stackoverflow.com/questions/39156017/c-what-is-time-complexity-of-qsort-function)

(2) sort

C++11 표준은 worst case에서 O(n log(n))의 복잡성을 요구한다.

이전 표준(C++03 등)에서는 worst case에서 O(n^2)을 허용했으며, average case에서 O(n logn)이기만 하면 되었다.

4. 실행 시간

STL의 sort는 C의 qsort보다 빠르다.

C++의 템플릿이 특정 데이터형과 비교 함수에 대해 최적화된 코드를 생성하기 때문이다.

sort는 직접 구현된 quicksort보다 20%~50% 빠르며, C의 qsort보다 250% ~ 1000% 빠르다고 한다(!).

특히 container가 int일 경우 std::less::operator()를 사용하며 인라인하여 정수를 직접 비교하게 된다.

반면 qsort는 매 비교마다 함수 포인터를 통해 간접 호출을 수행하기 때문에 최적화하기 힘들다.

100만개의 정수로 C++14에서 실험 결과, 

qsort: 0.247883 초 / sort: 0.086125 초

로 sort 함수가 훨씬 더 우수한 결과를 내었다고 한다.

5. 유연성

sort는 모든 데이터 유형과, C 배열, C++ 벡터, 다른 사용자정의 자료형 등 container에서 유연하게 작동한다.

C에서는 이런 여러 자료구조가 라이브러리에 포함되어 있지 않기 때문에 qsort는 단순히 배열을 기반으로 설계되었다.

그러므로 연속된 주소값을 가지는 모든 container에 대해 사용할 수 있는 sort 함수가 비교적 더 사용이 용이하다.

6. 안전성

qsort와 달리 비교적 안전하지 않은 void 포인터를 통해 데이터 항목에 엑세스할 필요가 없으므로, sort가 더 type-safe 하다.

공부하다 파생된 궁금점

(1) C++ 헤더파일은 왜 확장자가 없는가

참고자료: http://www.qaupot.com/wordpress/?p=2206

C++ 표준 라이브러리와 과거 표준 라이브러리(아마도 C의?)를 구분하기 위해,

C++ 표준 라이브러리의 확장자를 생략하기로 하였다고 한다.

참고로 본래 C 표준 라이브러리들은 접두사 c+ 헤더파일 명(확장자 없음)를 포함하여 쓸 수 있다.

(ex) cstdio, cstdlib 등

(2) qsort를 포함하는 헤더: algorithm vs cstdlib

줄곧 C++에서 qsort를 사용할때 algorithm 헤더 파일을 포함했었는데, 정작 qsort는 cstdlib에 정의되어 있었다.

왜 algorithm 헤더파일을 포함하면 qsort 함수를 쓸 수 있는지 궁금하여 계속 검색하였지만 찾을 수 없어 포기...하던 때였다.

위의 궁금점을 해결하기 위해 링크글을 보다가 "C++ 표준 라이브러리는 대부분 구현에 관련된 C 헤더를 포함"한다는 문구를 보게되었다.

그래서 algorithm 헤더도 qsort 함수가 포함된 cstdlib 헤더를 포함하고 있을 것이라 생각하였다.

실제로 algorithm > xmemory > xmemory0 를 따라가보니 cstdlib 헤더를 포함하고 있음을 확인할 수 있었다.

마찬가지로 iostream이나 algorithm(?) 헤더를 포함하는 것만으로도 printf 함수를 사용할 수 있는데,

iostream과 algorithm 헤더가 포함하는 헤더 파일들을 따라가다보면 cstdio 헤더파일을 포함하고 있기 때문임을 알 수 있었다.

(3) 라이브러리 vs 헤더 파일의 차이

참고자료: https://www.geeksforgeeks.org/difference-header-file-library/

ㅇㅇ