개요
C++은 예전에 멀티스레드를 공부하면서 조금 들여다본 정도가 전부다. 게임 서버를 만들 땐 Node.js가 주 언어였으니, C++은 “필요한 만큼만 열어봤던” 언어에 가깝다. 그러다 보니 문법을 제대로 정리해둔 적이 한 번도 없었다.. 이참에 C++ 정리 시리즈를 따로 열어두려 한다. 그 첫 편이 정렬이다.
바로 앞 Python - < 5 >에서 정렬 8종을 파이썬으로 정리했다. 이번 글은 같은 여덟 개를 C++로 옮긴 판이다. 그리고 코드트리에서 기수 정렬을 직접 구현하며 막혔던 세 지점을, 그때 물어봤던 순서 그대로 붙였다.
파이썬으로 쓸 땐 그냥 넘어갔던 게 C++에선 전부 손에 걸린다. 슬라이싱이 없어서 배열을 어디까지 볼 건지 인덱스로 직접 말해야 하고, 벡터를 그냥 넘기면 통째로 복사가 일어난다. 같은 알고리즘인데 코드 모양이 꽤 달라진다.
반복을 언제 멈출 것인가. 기수 정렬에서 세 번을 막혔는데, 세 번 다 이 질문으로 돌아왔다.
( 정렬 자체의 개념과 8종 비교표는 Python - < 5 >에 정리해뒀다. 여기서는 코드와 구현 이야기 위주로 간다. 강의 자료는 대외비라 슬라이드를 그대로 싣지 않고 개념만 직접 다시 그렸다 )
파이썬에서 넘어올 때 걸리는 것 셋
자리 바꾸기 - std::swap
파이썬에서는 a, b = b, a 한 줄이면 끝났다. C++에는 utility 헤더의 std::swap이 있다. iostream만 넣어도 대부분 딸려오지만, 명시적으로 쓰는 게 안전하다.
#include <utility>
std::swap(arr[j], arr[j + 1]);
파이썬이 오른쪽을 튜플로 묶었다 푸는 방식이라면, std::swap은 내부에서 이동(move)으로 두 값을 맞바꾼다. 큰 객체를 바꿔도 복사가 안 일어난다는 게 이쪽의 이점이다.
배열을 넘길 때 - 참조(&)
파이썬은 리스트를 넘기면 원본이 같이 바뀌었다. C++에서 vector<int> arr로 받으면 통째로 복사된다. 원본을 고치려면 참조로 받아야 한다. 이걸 빼먹으면 “정렬 함수를 호출했는데 원본이 그대로”인 상황이 나온다..
void bubbleSort(vector<int>& arr) // 원본이 바뀐다
void bubbleSort(vector<int> arr) // 복사본만 바뀐다
void bubbleSort(const vector<int>& arr) // 복사도 안 하고, 못 바꾸게 막는다
세 번째가 특히 편하다. 복사를 피하면서 “이 함수는 원본을 안 건드린다”를 시그니처로 선언해버린다. 파이썬에는 이걸 표현할 문법이 아예 없어서 주석이나 이름으로 약속하는 수밖에 없었다.
나눗셈 - 타입이 결정한다
파이썬은 정수 나눗셈이 //, 실수 나눗셈이 /로 나뉘어 있었다. C++은 양쪽 다 정수면 그냥 정수 나눗셈이다. 기호가 아니라 피연산자 타입이 동작을 정한다.
int a = 7 / 2; // 3 (둘 다 int)
double b = 7 / 2; // 3.0 (int로 계산한 뒤 대입한다!)
double c = 7.0 / 2; // 3.5 (한쪽이 double)
두 번째 줄이 함정이다. 받는 쪽이 double이라고 알아서 실수로 계산해주지 않는다. 기수 정렬에서 num / k를 쓸 때는 이게 오히려 편한데, 자릿수 계산이 그대로 정수로 떨어지기 때문이다.
C++에서 정렬을 옮기며 실수가 나오는 자리는 대개 셋 중 하나다 — 참조를 안 받았거나, 인덱스 범위를 잘못 줬거나, 나눗셈 타입을 착각했거나.
O(n²) 삼형제 — 버블 · 선택 · 삽입
셋 다 최악에 O(n²)다. 성격은 전부 다르다.
버블 정렬 - bubbleSort()
옆에 붙은 두 개를 비교해 순서가 틀렸으면 자리를 바꾼다. 한 바퀴 돌 때마다 가장 큰 값이 맨 뒤에 확정된다.
void bubbleSort(vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n; ++i)
{
// 뒤쪽 i칸은 이미 확정됐으니 볼 필요가 없다
for (int j = 0; j < n - i - 1; ++j)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
}
}
}
int n = arr.size()에서 int로 받은 이유가 있다. size()가 돌려주는 건 부호 없는 정수(size_t) 라서, n - i - 1이 음수가 되는 순간 0이 아니라 어마어마하게 큰 양수로 돌아버린다. C++을 처음 만지면 꼭 한 번 밟는 지뢰인 것 같다..
선택 정렬 - selectionSort()
남은 값 중 가장 작은 걸 골라 맨 앞에 놓는다. 한 패스에 교환이 딱 한 번이다.
void selectionSort(vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; ++i)
{
int minIdx = i;
// 뒤쪽 전체를 훑어 최솟값 위치를 찾는다
for (int j = i + 1; j < n; ++j)
{
if (arr[j] < arr[minIdx])
{
minIdx = j;
}
}
swap(arr[i], arr[minIdx]);
}
}
예전에 정리했던 글에서 여기 안쪽 반복문의 증가식을 j++가 아니라 i++로 써놨었다. 파이썬은 range(i + 1, n)이라 애초에 그런 실수를 할 자리가 없었는데, C++은 반복 변수를 사람이 직접 굴리니 그대로 실수할 수 있는 자리로 돌아온다. 안쪽 루프의 증가식은 항상 안쪽 변수여야 한다!
삽입 정렬 - insertionSort()
앞부분은 정렬된 상태로 두고, 뒤에서 값을 하나씩 꺼내 앞부분 안에 끼워 넣는다. 카드 정리하듯이.
void insertionSort(vector<int>& arr)
{
int n = arr.size();
for (int i = 1; i < n; ++i)
{
int current = arr[i];
int j = i - 1;
// current보다 큰 값들을 한 칸씩 뒤로 민다
while (j >= 0 && arr[j] > current)
{
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = current;
}
}
j >= 0 조건이 반드시 앞에 와야 한다. 순서를 바꾸면 arr[-1]을 읽는데, 파이썬처럼 맨 뒤 원소를 주는 게 아니라 그냥 배열 바깥 메모리를 읽는다. 에러도 안 나고 값도 그럴듯해서, C++에서 제일 조용하게 터지는 곳이다.
&&가 왼쪽부터 검사하다 거짓이면 오른쪽을 아예 안 보는 성질(단축 평가)에 안전이 걸려 있는 셈이다.
이미 정렬된 입력이면 while문이 한 번도 안 돌아 O(n)이 된다. O(n²) 중 유일하게 적응성을 가진 정렬이다.
카운팅 정렬 — 개수만 세고 끝낸다
값끼리 비교하지 않고 각 값이 몇 번 나왔는지만 센다.
vector<int> countingSort(const vector<int>& arr, int k)
{
int n = arr.size();
vector<int> count(k + 1, 0);
vector<int> result(n);
// 1) 값별 등장 횟수
for (int num : arr)
{
count[num]++;
}
// 2) 누적합 -> 각 값이 들어갈 마지막 자리
for (int i = 1; i <= k; ++i)
{
count[i] += count[i - 1];
}
// 3) 뒤에서부터 채운다
for (int i = n - 1; i >= 0; --i)
{
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return result;
}
vector<int> count(k + 1, 0) - C++은 크기와 초기값을 이렇게 같이 준다. 파이썬의 [0] * (k + 1)에 대응하는 자리다. 초기값을 빼도 int는 0으로 채워지지만, 명시하는 편이 읽기 좋다.
for (int num : arr) 는 범위 기반 for문이다. 파이썬의 for num in arr과 같은 모양인데, 여기서 num은 복사본이다. 값을 고쳐야 하면 for (int& num : arr)로 참조를 받아야 한다.
3번에서 뒤에서부터 도는 게 핵심이다. 앞에서부터 돌면 같은 값끼리 순서가 뒤집혀 안정성이 깨진다.
시간복잡도는 O(n + k)다. n은 개수, k는 값의 최댓값이다. n이 크고 k가 작을 때 강하고, 값이 하나라도 크면 그만큼의 벡터를 잡아야 해서 메모리로 손해를 본다.
기수 정렬 — 물어보면서 알게 된 것들
여기가 이번 글의 본론이다. 코드트리 [기수 정렬 구현] 문제를 푸는데, 알고리즘 자체보다 C++ 문법과 반복 조건에서 세 번 막혔다. 막힐 때마다 물어보며 풀었는데, 답보다 질문이 되돌아온 방식이 더 도움이 됐어서 그 과정을 그대로 적어둔다.
기수 정렬은 값 전체를 보지 않고 자릿수 하나씩 본다. 자릿수는 0~9뿐이니 버킷은 늘 열 개다.
막힌 곳 1 — ** 가 제곱이 아니다
자릿수를 뽑으려고 이렇게 썼다.
int number = (current[i] / (10 ** k)) % 10;
파이썬 습관이 그대로 나왔다. 파이썬에서 10 ** k는 10의 k제곱이지만, C++에는 ** 라는 연산자가 아예 없다. 그래서 “제곱은 math 라이브러리를 임포트해서 sqrt를 써야 하나?”를 물었는데, 여기서 두 개를 한 번에 정리했다.
| 함수 | 하는 일 | 헤더 |
|---|---|---|
pow(10, 3) |
10의 3제곱 → 1000 | cmath |
sqrt(100) |
100의 제곱근 → 10 | cmath |
sqrt는 제곱이 아니라 제곱근이다. 이름이 비슷해서 헷갈렸는데, 내가 필요한 건 pow 쪽이었다.
그런데 pow는 결국 안 썼다. 내가 필요한 값을 늘어놓고 보니 이랬기 때문이다.
1 → 10 → 100 → 1000
매번 10의 k제곱을 새로 계산할 게 아니라, 1을 하나 들고 있다가 한 바퀴 돌 때마다 10배하면 그만이었다.
int k = 1;
// ... 한 바퀴 끝날 때마다
k = k * 10;
pow는 부동소수점(double)을 다루는 함수라 정수 자릿수를 굴리는 데 쓰면 캐스팅이 붙는다. 애초에 필요가 없던 셈이다.
문법을 C++로 번역하려다 보니, 그 값이 정말 필요한지를 안 물어봤다.
10 ** k를 어떻게 쓰냐가 아니라 k 자체가 필요 없었다.
막힌 곳 2 — 자릿수를 세려다 k = 0에서 터졌다
다음 질문은 “가장 큰 수의 자릿수는 어떻게 구하지?”였다. 자릿수가 4자리면 네 바퀴를 돌아야 하니, 먼저 몇 자리인지 알아야 한다고 생각한 것이다.
그래서 k를 자릿수 번호로 뒀다. k = 0이면 1의 자리, k = 1이면 10의 자리. 그런데 이러면 나눗셈이 안 된다.
// k를 자릿수 "번호"로 두면
int number = (current[i] / k) % 10; // k = 0 -> 0으로 나누기!
여기서 방향이 바뀌었다. k를 번호(0, 1, 2) 로 세는 대신 자릿수 값(1, 10, 100) 자체를 담으면, 시작값이 0이 아니라 1이라 나눗셈이 애초에 안 터진다. 막힌 곳 1에서 k = k * 10으로 굴리기로 한 그 변수가 그대로 답이었다.
그리고 자릿수를 직접 셀 필요도 없었다. 최댓값을 현재 자릿수로 나눠보면 된다.
| 나눗셈 | 결과 | 뜻 |
|---|---|---|
| 5837 / 1 | 5837 | 1의 자리 볼 것 있음 |
| 5837 / 10 | 583 | 10의 자리 볼 것 있음 |
| 5837 / 100 | 58 | 100의 자리 볼 것 있음 |
| 5837 / 1000 | 5 | 1000의 자리 볼 것 있음 |
| 5837 / 10000 | 0 | 더 볼 자릿수가 없다 |
maxValue / k가 0이 되는 순간이 곧 끝이다. “몇 자리인가”를 구해서 세는 게 아니라, “아직 남았는가”를 매번 묻는 것으로 바뀌었다.
개수를 미리 세려 하지 말고, 끝났는지를 물어라. 자릿수뿐 아니라 반복문 전반에 쓸 수 있는 얘기 같다.
막힌 곳 3 — 탈출 조건을 “현재 자리가 전부 0”으로 잡았다
처음 짠 탈출 조건은 이거였다.
지금 보고 있는 자릿수가 모든 값에서 0이면, 더 볼 게 없으니 끝
그럴듯해 보였다. 1의 자리, 10의 자리를 훑다가 어느 순간 전부 0이 되면 끝이라는 논리다. 그런데 이건 틀린다.
[300, 100, 200]을 넣어보면 바로 드러난다. 1의 자리가 처음부터 전부 0이라 첫 바퀴에서 종료 조건에 걸린다. 정작 봐야 할 백의 자리는 구경도 못 하고, 결과는 [300, 100, 200] 그대로다.
“현재 자리가 0”인 건 아직 그 자리까지 안 왔다는 뜻일 수도 있다. 끝났다는 뜻이 아니다. 이 둘을 구분하려면 기준을 현재 자리가 아니라 가장 큰 값에 둬야 한다. 막힌 곳 2에서 나온 maxValue / k == 0이 정확히 그 기준이다.
int k = 1;
// 탈출 조건 = 자릿수 k가 가장 큰 값의 자릿수보다 클 때
while (maxValue / k > 0)
{
vector<vector<int>> digits(10, vector<int>());
// 현재 자릿수로 버킷에 분배
for (int i = 0; i < n; ++i)
{
int number = (current[i] / k) % 10;
digits[number].push_back(current[i]);
}
// 0번 버킷부터 순서대로 다시 꺼낸다
current.clear();
for (int i = 0; i < 10; ++i)
{
current.insert(
current.end(),
digits[i].begin(),
digits[i].end()
);
}
k = k * 10;
}
왜 이게 되는가
10의 자리로 다시 담을 때 1의 자리 정렬이 안 망가지는 이유는, 버킷에 앞에서부터 넣고 앞에서부터 꺼내기 때문이다. push_back으로 넣고 insert로 순서대로 이어붙이는 이 방식 자체가 안정 정렬이다. 안정 정렬을 낮은 자릿수부터 겹쳐 쓰면 앞선 결과가 그대로 살아남는다.
기수 정렬은 안정성 위에 서 있다. 중간에 한 번이라도 순서를 뒤집으면 그냥 틀린 답이 나온다.
시간복잡도는 O(d(n + k))다. d는 자릿수, k는 버킷 개수 10. 자릿수가 짧으면 사실상 선형이다.
분할 정복 3종 — 병합 · 퀵 · 힙
파이썬 편과 달리 여기서는 인덱스로 구간을 잘라 쓰는 방식으로 적었다. 슬라이싱이 없으니 복사를 줄이려면 이게 자연스럽다.
병합 정렬 - mergeSort()
void mergeSort(vector<int>& arr, int left, int right)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
vector<int> tmp;
int i = left, j = mid + 1;
while (i <= mid && j <= right)
{
// 같은 값이면 왼쪽 먼저 -> 안정성이 여기서 나온다
if (arr[i] <= arr[j]) tmp.push_back(arr[i++]);
else tmp.push_back(arr[j++]);
}
while (i <= mid)
{
tmp.push_back(arr[i++]);
}
while (j <= right)
{
tmp.push_back(arr[j++]);
}
for (int t = 0; t < (int)tmp.size(); ++t)
{
arr[left + t] = tmp[t];
}
}
파이썬은 arr[:mid]로 반을 잘라 넘겼지만, C++은 자르지 않고 “여기부터 저기까지”를 인덱스로 알려준다. 복사를 안 하니 그만큼 빠르다. 대신 left, right를 인자로 받아야 해서 호출부가 mergeSort(arr, 0, n - 1)처럼 길어진다.
<=가 <였다면 같은 값일 때 오른쪽을 먼저 가져와 안정성이 깨진다. 등호 하나가 성질을 바꾸는 자리다.
최악에도 O(n log n)이 보장되고 안정 정렬이다. 대신 합칠 자리(tmp)를 매번 잡는다.
퀵 정렬 - quickSort()
void quickSort(vector<int>& arr, int left, int right)
{
if (left >= right)
{
return;
}
int pivot = arr[(left + right) / 2];
int i = left, j = right;
while (i <= j)
{
while (arr[i] < pivot)
{
++i;
}
while (arr[j] > pivot)
{
--j;
}
if (i <= j)
{
swap(arr[i++], arr[j--]);
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
파이썬에서는 리스트 컴프리헨션으로 세 줄이면 끝났는데, 대신 매번 새 리스트를 만들어서 제자리 정렬이 아니었다. C++의 이 방식은 배열 안에서 인덱스 두 개를 마주 보게 굴려 자리를 바꾸므로 추가 메모리를 안 쓴다. 원래 퀵 정렬의 모습이 이쪽이다.
피벗을 가운데로 잡았다. 첫 값으로 잡으면 이미 정렬된 입력에서 한쪽이 텅 비어 O(n²)로 떨어진다.
힙 정렬 - heapSort()
void heapify(vector<int>& arr, int i, int size)
{
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && arr[left] > arr[largest])
{
largest = left;
}
if (right < size && arr[right] > arr[largest])
{
largest = right;
}
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, largest, size);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; --i)
{
heapify(arr, i, n);
}
for (int i = n - 1; i > 0; --i)
{
swap(arr[0], arr[i]);
heapify(arr, 0, i);
}
}
추가 메모리를 안 쓰면서 최악에도 O(n log n)이다. 대신 멀리 떨어진 값끼리 교환해서 안정성이 없다.
C++에도 우선순위 큐가 이미 있다. std::priority_queue는 기본이 최대 힙이라 큰 값부터 나온다. 파이썬의 heapq가 최소 힙만 지원해서 마이너스를 붙여 쓰던 것과 정반대라, 두 언어를 오가면 꼭 한 번 헷갈린다..
그래서 실무에서는 std::sort 한 줄이다
여덟 개를 다 짜보고 나니, C++ 표준 라이브러리가 왜 저렇게 생겼는지가 보였다.
#include <algorithm>
sort(arr.begin(), arr.end()); // 오름차순
sort(arr.begin(), arr.end(), greater<int>()); // 내림차순
stable_sort(arr.begin(), arr.end()); // 안정 정렬이 필요할 때
| 함수 | 실제 구현 | 최악 | 안정성 | 언제 쓰나 |
|---|---|---|---|---|
| std::sort | 인트로소트 (퀵 + 힙 + 삽입) | O(n log n) | X | 기본값. 그냥 이걸 쓴다 |
| std::stable_sort | 병합 기반 | O(n log n) | O | 앞선 정렬 순서를 지켜야 할 때 |
| std::partial_sort | 힙 기반 | O(n log k) | X | 상위 k개만 필요할 때 |
std::sort의 인트로소트(introsort) 가 재밌다. 퀵 정렬로 가다가, 재귀가 너무 깊어지면( 즉 피벗을 계속 잘못 골라 최악으로 가고 있으면 ) 힙 정렬로 갈아탄다. 그리고 구간이 충분히 작아지면 삽입 정렬로 마무리한다.
- 퀵 정렬의 평균 속도를 쓰되
- 힙 정렬로 최악 O(n²)를 막고
- 삽입 정렬로 작은 구간의 적응성을 챙긴다
앞의 여덟 개가 서로의 약점을 그대로 메우고 있어서, 다 짜보고 나서야 이 설계가 이해가 됐다!
정렬 기준을 주는 법
struct Student { string name; int grade; int score; };
// 학년 오름차순, 같은 학년이면 점수 내림차순
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
if (a.grade != b.grade) return a.grade < b.grade;
return a.score > b.score;
});
파이썬의 key=lambda s: (s[1], -s[2])가 “무엇으로 세울지” 를 주는 방식이라면, C++의 비교 함수는 “누가 앞에 오는지” 를 직접 답하는 방식이다. 그래서 문자열 내림차순처럼 마이너스를 못 붙이는 경우도 C++에서는 그냥 부등호를 뒤집으면 된다.
다만 이 비교 함수는 “a가 b보다 엄격히 앞서는가” 를 돌려줘야 한다. 같을 때 true를 돌려주면( <=를 쓰면 ) 정렬이 무한히 돌거나 프로그램이 죽는다. 파이썬 key에는 없던 종류의 함정이다.
여덟 개를 직접 짤 이유는 실무에서 쓰려고가 아니라, std::sort 안에서 무슨 일이 일어나는지 알기 위해서였다.
다른 언어와 견줘 보면
이번에 같은 정렬을 두 언어로 옮기며 겹쳐 보였던 지점들을 정리해둔다.
| 개념 | C++ | Python / 익숙한 다른 문법 |
|---|---|---|
| 자리 바꾸기 | std::swap(a, b) | a, b = b, a |
| 원본을 바꾸기 | 참조로 받기 vector |
리스트는 기본이 참조 |
| 원본을 안 바꾼다고 선언 | const vector |
표현할 문법이 없다 |
| 정수 나눗셈 | int / int (타입이 결정) | num // k (기호가 결정) |
| 구간 넘기기 | (arr, left, right) 인덱스 | arr[:mid] 슬라이싱 |
| 2차원 컨테이너 | vector<vector |
[[] for _ in range(10)] |
| 표준 정렬 | std::sort = 인트로소트 | sorted() = Timsort |
| 안정 정렬 | std::stable_sort (따로 불러야) | sorted() (기본이 안정) |
| 정렬 기준 | 비교 함수 (누가 앞이냐) | key= (무엇으로 세우냐) |
| 우선순위 큐 | priority_queue (기본 최대 힙) | heapq (최소 힙만) |
특히 재밌었던 건 std::sort와 sorted()가 정반대 선택을 했다는 점이다. 파이썬은 메모리를 내주고 안정성과 적응성을 챙겼고( Timsort ), C++은 안정성을 버리고 메모리를 아꼈다( 인트로소트 ). 안정성이 필요하면 stable_sort를 따로 부르라는 게 C++의 태도다.
“기본값을 뭘로 둘 것인가”에 언어의 성격이 그대로 드러나는 것 같다. 편의를 기본으로 두는 쪽과, 비용을 기본으로 두고 필요하면 더 내라는 쪽.
한줄 평
- 같은 정렬 이론임에도, 언어에 따라 다른 특성들이나 호환 방식이 달라 재밌었다.