C++ 표준 라이브러리(STL)에서 가장 자주 사용되는 알고리즘 중 하나인 std::sort()는 이름 그대로 컨테이너나 배열의 요소들을 오름차순으로 정렬해 주는 함수입니다. 겉보기에는 간단해 보이지만, 내부적으로는 상당히 정교한 알고리즘이 숨어 있습니다.
std::sort()의 핵심: IntroSort 알고리즘
std::sort()는 단순히 퀵 정렬(Quick Sort)만 사용하는 것이 아니라, IntroSort(Introspective Sort)라는 하이브리드 알고리즘을 기반으로 동작합니다. IntroSort는 다음 세 가지 정렬 알고리즘을 상황에 따라 조합하여 사용합니다.
- 퀵 정렬(Quick Sort): 기본적인 분할 정복 방식으로 빠른 평균 성능을 제공합니다.
- 힙 정렬(Heap Sort): 재귀 깊이가 너무 깊어져 최악의 경우(O(n²))로 빠질 위험이 감지되면 전환됩니다.
- 삽입 정렬(Insertion Sort): 요소 개수가 적은 구간에서는 오버헤드가 적은 삽입 정렬이 더 효율적입니다.
이러한 하이브리드 구조 덕분에 std::sort()는 평균 및 최악의 경우 모두 O(n log n)의 시간 복잡도를 보장하며 안정적인 성능을 발휘합니다.
기본 사용 예제
아래 예제는 std::sort()를 사용하여 정수 배열을 기본 비교 기준(오름차순)으로 정렬하는 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
int n = sizeof(arr) / sizeof(arr[0]);
// arr부터 arr+n까지의 범위를 정렬
sort(arr, arr + n);
cout << "\nArray after sorting using default sort is : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}실행 결과
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9
정리
std::sort()는 두 개의 반복자(iterator) 인자를 받아 해당 범위의 요소들을 정렬합니다. 별도의 비교 함수를 지정하지 않으면 < 연산자를 기준으로 오름차순 정렬이 수행되며, 필요하다면 사용자 정의 비교 함수나 람다식을 세 번째 인자로 전달하여 내림차순 등 다양한 기준으로 정렬할 수 있습니다. IntroSort 기반의 최적화된 구현 덕분에 대용량 데이터에서도 신뢰할 만한 성능을 기대할 수 있습니다.