이번 튜토리얼에서는 C++ STL(표준 템플릿 라이브러리)을 활용하여 삽입 정렬(Insertion Sort)을 구현하는 방법을 살펴보겠습니다.
일반적인 삽입 정렬은 이중 반복문을 사용하지만, STL을 활용하면 훨씬 간결하고 안전한 코드를 작성할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
std::upper_bound를 사용해 현재 원소가 들어가야 할 올바른 위치(정렬된 구간 내에서 처음으로 더 큰 값이 나오는 지점)를 찾습니다.std::rotate를 사용해 배열의 미정렬 구간을 회전시켜 해당 원소를 올바른 자리에 삽입합니다.
예제 코드
#include <bits/stdc++.h>
//삽입 정렬을 수행하는 함수
void insertionSort(std::vector<int> &vec){
for (auto it = vec.begin(); it != vec.end(); it++){
auto const insertion_point =
std::upper_bound(vec.begin(), it, *it);
std::rotate(insertion_point, it, it+1);
}
}
//배열을 출력하는 함수
void print(std::vector<int> vec){
for( int x : vec)
std::cout << x << " ";
std::cout << '\n';
}
int main(){
std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
insertionSort(arr);
print(arr);
return 0;
}
실행 결과
1 2 3 4 5 5 6 7
코드 동작 원리
insertionSort 함수는 벡터의 처음부터 끝까지 반복자(it)를 이동시키며 각 원소를 처리합니다.
- 삽입 위치 탐색:
std::upper_bound(vec.begin(), it, *it)는 이미 정렬된 구간[begin, it)내에서 현재 원소*it보다 큰 첫 번째 원소의 위치를 반환합니다. 덕분에 중복 값이 있어도 안정 정렬(stable sort)이 유지됩니다. - 구간 회전:
std::rotate(insertion_point, it, it+1)은 삽입 지점부터 현재 원소까지의 구간을 한 칸 회전시켜, 현재 원소를 정확히 삽입 위치에 놓습니다.
이처럼 STL 알고리즘을 조합하면 직접 인덱스를 다루는 것보다 버그 발생 가능성이 낮고 가독성이 뛰어난 삽입 정렬 코드를 작성할 수 있습니다. 시간 복잡도는 기존 삽입 정렬과 동일하게 평균 및 최악의 경우 O(n²), 이미 정렬된 데이터에 대해서는 O(n)입니다.