C와 C++의 병합 정렬(merge sort)
이 레슨에서는 항상 O(n log n)에 실행되는 분할 정복 전략의 병합 정렬을 구현합니다.
소개
병합 정렬은 배열을 두 절반으로 나누고, 재귀 호출로 각각 정렬한 다음, 정렬된 두 절반을 하나의 정렬된 수열로 합칩니다. 입력 데이터의 상태와 상관없이 실행 시간이 항상 O(n log n)으로 안정적이라는 것이 큰 장점입니다.
핵심 정리
- 빈 입력, 요소 하나, 중복 값, 이미 정렬된 데이터로 테스트하세요.
- 먼저 코드가 올바르게 동작하게 만든 다음 최적화하세요.
- 실제 코드에서는 표준 라이브러리의 이미 만들어진 함수를 우선 쓰세요.
C와 C++의 병합 정렬(merge sort) 시각화
O(n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
C와 C++ 코드 예제
C
main.c
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int *values, int *temporary, int left, int right) {
if (right - left < 2) return;
int middle = (left + right) / 2;
merge_sort(values, temporary, left, middle);
merge_sort(values, temporary, middle, right);
int first = left;
int second = middle;
int output = left;
while (first < middle && second < right) {
temporary[output++] = values[first] < values[second]
? values[first++] : values[second++];
}
while (first < middle) temporary[output++] = values[first++];
while (second < right) temporary[output++] = values[second++];
for (int index = left; index < right; ++index) {
values[index] = temporary[index];
}
}
int main(void) {
int values[] = {8, 3, 6, 2, 7};
int temporary[5];
merge_sort(values, temporary, 0, 5);
for (int index = 0; index < 5; ++index) {
printf("%d ", values[index]);
}
}
2 3 6 7 8C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
void merge_sort(std::vector<int>& values) {
if (values.size() < 2) return;
auto middle = values.begin() + values.size() / 2;
std::vector<int> left(values.begin(), middle);
std::vector<int> right(middle, values.end());
merge_sort(left);
merge_sort(right);
std::merge(left.begin(), left.end(), right.begin(), right.end(),
values.begin());
}
int main() {
std::vector values{8, 3, 6, 2, 7};
merge_sort(values);
for (int value : values) {
std::cout << value << ' ';
}
}
2 3 6 7 8C와 C++ 비교
C의 merge_sort 함수는 구간의 요소가 2개보다 적으면 멈춥니다. 두 절반을 정렬한 뒤 while 반복문이 두 맨 앞 요소 중 더 작은 쪽을 골라 임시 배열 temporary에 복사하고, 마지막에 남은 것을 복사합니다. 두 버전 모두 O(n)의 추가 메모리가 필요합니다. C 버전은 임시 배열을 직접 관리하고, C++ 버전은 vector와 표준 알고리즘으로 코드를 더 알기 쉽게 만듭니다.
C
반복문, 포인터, 길이, 임시 버퍼를 모두 명시적으로 작성합니다.
C++
반복자와 표준 알고리즘이 처리 방식과 데이터를 저장하는 방식을 분리합니다.
연습 문제
두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.
- 종이에 비교 과정을 하나씩 따라가 보세요.
- 중복 값과 아주 크거나 작은 값으로 테스트해 보세요.
- 직접 작성한 코드의 실행 시간을 재고 표준 라이브러리와 비교해 보세요.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지