– 힙 정렬 · 병합 정렬 · 기수 정렬 –
정렬 알고리즘 중 고급 알고리즘들은 일반적인 O(N²) 방식보다 훨씬 빠르고
대용량 데이터 처리에 매우 효율적이다.
이번 글에서는 대표적인 **힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 기수 정렬(Radix Sort)**을
1편과 동일하게 원리 → 시각화 → C 코드 → 시간 복잡도 → 특징 순서로 정리해본다.
- 힙 정렬 (Heap Sort)
힙 정렬은 완전 이진 트리 기반의 자료구조인 힙(Heap)을 이용하여 정렬한다.
원리
1. 배열을 최대 힙(Max Heap)으로 구성한다.
2. 루트(최댓값)를 맨 뒤로 이동한다.(swap)
3. 힙의 크기를 줄이고 다시 힙 구성
4. 반복하여 정렬 완성
시각화 (글 형태)
초기 배열:
[5, 3, 8, 4, 2, 7]
→ 최대 힙 구성
[8, 4, 7, 3, 2, 5]
→ 루트 8을 맨 뒤로 이동
[5, 4, 7, 3, 2 | 8]
→ 다시 힙 구성
[7, 4, 5, 3, 2 | 8]
→ 반복하여 완성
[2, 3, 4, 5, 7, 8]
코드 예제 (C언어)
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heap_sort(int arr[], int n) {
// 최대 힙 구성
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 하나씩 요소 추출
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
시간 복잡도
| 최악 | O(N log N) |
| 평균 | O(N log N) |
| 최선 | O(N log N) |
| 공간 복잡도 | O(1) |
특징
1. 최악의 경우에도 항상 O(N log N) — 안정적 속도
2. 추가 메모리가 거의 필요 없음
3. 병합 정렬보다 메모리 효율적
4. 하지만 재귀 호출이 많아서 실제 성능이 퀵정렬보다 느리기도 함
- 병합 정렬 (Merge Sort)
병합 정렬은 분할 정복(Divide and Conquer) 알고리즘이다.
원리
1. 배열을 반으로 나눈다.
2. 각각 재귀적으로 정렬
3. 두 배열을 "병합(merge)" 하면서 정렬된 배열을 만든다.
시각화 (글 형태)
[8, 3, 5, 4, 7, 6, 2, 1]
→ 반으로 분할
[8, 3, 5, 4] / [7, 6, 2, 1]
→ 다시 분할
[8, 3] / [5, 4] / [7, 6] / [2, 1]
→ 정렬 후 병합
[3, 8] + [4, 5] → [3, 4, 5, 8]
[6, 7] + [1, 2] → [1, 2, 6, 7]
→ 최종 병합
[1, 2, 3, 4, 5, 6, 7, 8]
코드 예제 (C언어)
void merge(int arr[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
int temp[right - left + 1];
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (int t = 0; t < k; t++)
arr[left + t] = temp[t];
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
시간 복잡도
| 최선 | O(N log N) |
| 평균 | O(N log N) |
| 최악 | O(N log N) |
| 공간 복잡도 | O(N) |
특징
1. 최악/평균/최선 모두 O(N log N)의 안정적인 알고리즘
2. 대용량 데이터 정렬에 매우 효율적
3. 추가 배열(메모리)이 필요 → 공간 효율은 낮음
4. 안정 정렬(Stable Sort) 특성이 있음
- 기수 정렬
기수 정렬은 비교 기반이 아니라 숫자의 자릿수(digit) 단위로 정렬하는 방식이다.
원리
1. 1의 자리 → 10의 자리 → 100의 자리 순으로 정렬
2. 기본적으로 계수 정렬(Counting Sort)을 보조로 사용한다.
시각화 (글 형태)
정렬 대상: [170, 45, 75, 90, 802, 24, 2, 66]
1. 1의 자리 기준 정렬 → [170, 90, 802, 2, 24, 45, 75, 66]
2. 10의 자리 기준 정렬 → [802, 2, 24, 45, 66, 170, 75, 90]
3. 100의 자리 기준 정렬 → [2, 24, 45, 66, 75, 90, 170, 802]
코드 예제 (C언어)
int get_max(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void counting_sort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radix_sort(int arr[], int n) {
int max = get_max(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
counting_sort(arr, n, exp);
}
시간 복잡도
N = 정렬할 데이터 수
K = 가장 큰 수의 자리 수
| 시간 복잡도 | O(N x K) |
| 공간 복잡도 | O(N + K) |
특징
1. 비교 기반이 아니라 자릿수 기반
2. 특정 상황(데이터 범위가 작거나 정수 형태)에선 매우 빠름
3. 숫자가 매우 큰 경우에는 비효율적
4. 실무에선 특수 목적용으로 사용됨
고급 정렬 알고리즘 비교 표
| 알고리즘 | 평균 속도 | 최악 속도 | 공간 복잡도 | 특징 |
| 힙 정렬 | O(N log N) | O(N log N) | O(1) | 메모리 효율적, 안정 정렬 아님 |
| 병합 정렬 | O(N log N) | O(N log N) | O(N) | 매우 안정적, 안정 정렬 |
| 기수 정렬 | O(NK) | O(NK) | O(N + K) | 비교 없이 자릿수 기반 |
이번 두 편의 글을 통해 기본적인 선택·버블·삽입·퀵 정렬부터 보다 고급스러운 힙·병합·기수 정렬까지 대표적인 정렬 알고리즘을 한 번에 정리해보았다.
정렬은 단순히 데이터를 오름차순으로 나열하는 기술이 아니라, 컴퓨터가 정보를 어떻게 비교하고, 어떻게 구조화하고, 어떻게 효율을 극대화하는지를 보여주는 핵심 개념이다.
정렬 알고리즘의 차이는 곧 시간 복잡도와 공간 복잡도의 차이이며, 이 선택은 프로그램의 성능을 좌우하는 중요한 판단 기준이 된다.
각 알고리즘의 원리·시각화·C 코드·복잡도를 함께 살펴본 만큼, 앞으로 새로운 문제를 만났을 때 가장 적절한 정렬 알고리즘을 스스로 선택할 수 있게 되었기를 바란다.
정렬은 알고리즘 학습의 출발점이다.
앞으로 그래프 탐색, 동적 계획법, 해시, 트리, 우선순위 큐 같은 더 깊은 영역을 공부할 때에도
이번에 다룬 정렬 개념들은 계속해서 중요한 기반이 되어줄 것이다.