C++ STL(표준 템플릿 라이브러리)의 stable_sort() 함수는 지정된 범위의 요소들을 키(key)를 기준으로 오름차순으로 정렬하는 알고리즘입니다. 일반적인 sort() 함수와 달리, stable_sort()는 안정성(stability)을 보장한다는 점이 핵심 특징입니다. 즉, 값이 동일한 요소들이 원본 데이터에서 가졌던 상대적인 순서가 정렬 후에도 그대로 유지됩니다.
예를 들어, 학생 데이터를 이름순으로 먼저 정렬한 뒤 점수순으로 다시 정렬할 때, 이름순 정렬 결과가 보존됩니다. 이러한 특성 덕분에 복합 조건 정렬이 필요한 상황에서 stable_sort()가 매우 유용하게 활용됩니다.
stable_sort()의 주요 특징
- 안정성 보장: 동등한(equivalent) 요소들의 원래 상대적 순서가 정렬 후에도 유지됩니다.
- 시간 복잡도: 추가 메모리가 충분히 확보되면 O(N log N), 메모리가 부족하면 최악의 경우 O(N log²N)의 성능을 보입니다.
- 사용법: sort()와 마찬가지로 정렬할 범위의 시작 반복자와 끝 반복자를 인자로 전달합니다.
예제 코드
다음은 C++ 프로그램에서 stable_sort() 알고리즘을 활용하여 정수 배열을 정렬하는 예제입니다.
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = { 11, 15, 18, 19, 16, 17, 13, 20, 14, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
stable_sort(arr, arr + n);
cout << "Array after sorting is =";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
코드 설명
- 크기 11의 정수 배열
arr을 선언하고 무작위 숫자로 초기화합니다. sizeof(arr) / sizeof(arr[0])연산을 통해 배열의 전체 크기를 계산하여n에 저장합니다.stable_sort(arr, arr + n)호출로 배열의 처음부터 끝까지 오름차순 정렬을 수행합니다.- for 루프를 사용하여 정렬 완료된 배열의 모든 요소를 순서대로 출력합니다.
실행 결과
프로그램을 실행하면 아래와 같이 배열이 오름차순으로 정렬된 결과를 확인할 수 있습니다.
Array after sorting is= 10 11 12 13 14 15 16 17 18 19 20
마무리
stable_sort()는 단순히 정렬 기능만 제공하는 것이 아니라, 동일한 값 사이의 순서까지 보장해야 하는 실무 환경에서 강력한 도구입니다. 정렬 안정성이 중요하지 않은 경우에는 성능상 약간 더 유리한 sort()를, 순서 보존이 필요한 경우에는 stable_sort()를 선택하는 것이 바람직합니다.