이 글에서는 C 언어의 qsort() 함수와 C++의 sort() 함수가 어떻게 다른지 자세히 살펴보겠습니다. 두 함수 모두 배열을 정렬하는 데 사용되지만, 내부 동작 방식, 성능, 안전성 측면에서 중요한 차이점이 있습니다.
C의 qsort() 함수
C 표준 라이브러리는 qsort() 함수를 제공하여 배열을 정렬할 수 있습니다. 이 함수의 원형과 매개변수 구조는 다음과 같습니다.
void qsort(void *base, size_t num, size_t size, int (*comparator) (const void*, const void*));
qsort()는 네 가지 인자를 받습니다.
- base: 정렬할 배열의 시작 주소
- num: 배열에 포함된 요소의 개수
- size: 각 요소의 크기(바이트 단위)
- comparator: 두 요소를 비교하는 비교 함수 포인터
C++의 sort() 함수
C++은 STL(표준 템플릿 라이브러리)에 sort() 함수를 제공합니다. 이 함수의 원형은 다음과 같습니다.
void sort(T first, T last, Compare c);
참고로 sort()는 값이 같은 반복 요소들의 상대적 순서가 유지됨을 보장하지 않습니다. 안정적인 순서 유지가 필요하다면 C++ STL에서 제공하는 stable_sort()를 사용해야 합니다.
qsort()와 sort()의 주요 차이점
| C의 qsort() | C++의 sort() |
|---|---|
| 퀵소트(quicksort) 알고리즘을 사용합니다. | 인트로소트(introsort)를 사용합니다. 이는 하이브리드 정렬 알고리즘으로, 구현 방식에 따라 서로 다른 알고리즘이 적용됩니다. GNU C++ STL은 인트로소트, 퀵소트, 삽입 정렬을 결합한 3단계 하이브리드 정렬 방식을 채택하고 있습니다. |
| C 표준은 이 정렬 알고리즘의 시간 복잡도를 명시하지 않습니다. | C++11의 sort()는 최악의 경우에도 O(n log n)의 시간 복잡도를 보장합니다. 일부 이전 버전의 sort()는 최악의 경우 O(n²), 평균적으로 O(n log n)의 성능을 보였습니다. |
| 실행 시간이 sort()보다 깁니다. | 실행 시간이 qsort()보다 짧습니다. |
| 다양한 종류의 데이터에 대한 유연성이 떨어집니다. | 매우 유연합니다. C 배열, C++ 벡터(vector), 덱(deque) 등 다양한 컨테이너를 모두 정렬할 수 있습니다. |
| 타입 안전성이 낮습니다. 데이터 접근에 안전하지 않은 void 포인터를 사용합니다. | 더욱 안전합니다. 데이터 접근에 위험한 void 포인터가 필요하지 않습니다. |
결론
정리하면, C++의 sort()는 타입 안전성, 최악의 경우에도 보장되는 O(n log n) 성능, 다양한 컨테이너 지원 등 여러 면에서 C의 qsort()보다 우수합니다. 따라서 C++ 환경에서 개발할 때는 STL의 sort()를 사용하는 것이 바람직하며, 동일한 값의 요소들 간 원래 순서를 유지해야 하는 경우에는 stable_sort()를 활용하면 됩니다.