고급 정렬: 퀵·힙·병합·기수 | 정보처리기사 필기

네 알고리즘을 구분하는 기준

이하의 설명과 배열 추적은 오름차순 정렬의 대표적인 배열 구현을 기준으로 한다. 퀵 정렬의 구체적인 추적은 마지막 원소를 피벗으로 삼아 피벗을 최종 위치에 두는 로무토 분할, 기수 정렬은 낮은 자릿수부터 처리하는 LSD 방식을 사용한다. 퀵·힙·병합 정렬은 원소의 대소를 비교하는 비교 정렬이고, 기수 정렬은 키의 자릿값을 이용해 분배하는 비비교 정렬이다.

네 알고리즘은 한 단계가 끝났을 때 보장되는 상태부터 구분하면 혼동이 줄어든다.

알고리즘	한 단계의 핵심 동작	단계 뒤 보장되는 상태
퀵 정렬	피벗을 기준으로 한 번 분할	피벗의 최종 위치가 확정됨. 양쪽 부분 배열 자체는 아직 정렬되지 않을 수 있음
힙 정렬	최대 힙의 루트와 힙의 마지막 원소를 교환	현재 최댓값이 정렬 완료 구간의 맨 앞에 확정됨
병합 정렬	이미 정렬된 두 구간을 병합	두 구간을 합친 더 큰 구간이 정렬됨. 개별 원소의 전체 최종 위치는 마지막 병합 전까지 달라질 수 있음
LSD 기수 정렬	현재 자릿수로 안정적으로 분배·수집	지금까지 처리한 낮은 자릿수들의 순서가 맞음. 가장 높은 자릿수까지 끝나야 전체 정렬 완료

시간·공간·안정성 비교

다음 표는 시험에서 주로 다루는 표준 구현의 성질이다. 안정 정렬은 같은 키를 가진 원소의 입력 순서를 보존하며, 보조 공간은 입력 저장 공간 외에 추가로 사용하는 작업 공간이다. 변형 알고리즘이나 구현 최적화에 따라 세부 공간 사용량은 달라질 수 있다.

알고리즘	대표 시간 복잡도	대표 보조 공간	안정성	핵심 조건
퀵 정렬	최선·평균 Θ(n log n), 최악 Θ(n²)	분할 O(1) + 호출 스택 평균 Θ(log n), 최악 Θ(n)	일반적으로 불안정	분할 균형과 피벗 선택에 영향받음
힙 정렬	평균·최악 Θ(n log n), 모든 입력 O(n log n)	O(1)	불안정	오름차순은 최대 힙을 사용해 큰 값부터 뒤에 확정
병합 정렬	최선·평균·최악 Θ(n log n)	표준 배열 구현 Θ(n)	안정적으로 구현 가능	동률일 때 왼쪽 구간 원소를 먼저 선택
LSD 기수 정렬	대표적으로 Θ(d(n+k))	대표적으로 Θ(n+k)	자릿수 단계가 안정적이면 안정적	d는 자릿수 수, k는 자릿값 종류 수

퀵 정렬은 흔히 제자리 정렬로 분류되지만, 이는 분할 과정이 원소 수에 비례하는 별도 배열을 만들지 않는다는 뜻이다. 재귀 호출 스택까지 계산하면 평균 Θ(log n), 최악 Θ(n)의 추가 공간이 필요할 수 있다.

안정 정렬은 같은 키의 기존 순서를 보존한다. 여러 키를 순차 정렬하여 우선순위를 만들 때는 낮은 우선순위부터 처리하고 마지막에 가장 높은 우선순위 키로 안정 정렬한다.

퀵 정렬

퀵 정렬(Quick Sort)은 피벗(pivot)을 하나 선택한 뒤, 피벗보다 작은 쪽과 큰 쪽으로 원소를 나누는 분할(partition)을 수행한다. 동률을 어느 쪽에 둘지와 피벗을 직접 최종 위치에 놓을지는 분할 방식에 따라 달라진다. 분할 뒤에는 생성된 부분 배열에 같은 과정을 재귀적으로 적용한다.

분할과 정렬은 다르다

아래 예시는 마지막 원소를 피벗으로 사용하는 로무토(Lomuto) 분할 방식이다. 피벗은 3, 입력은 [5, 2, 8, 1, 3]이다.

단계	배열 상태	의미
시작	`[5, 2, 8, 1, 3]`	마지막 원소 `3`을 피벗으로 선택
`2` 처리	`[2, 5, 8, 1, 3]`	`3` 이하인 `2`를 왼쪽 구간으로 이동
`1` 처리	`[2, 1, 8, 5, 3]`	`3` 이하인 `1`을 왼쪽 구간으로 이동
피벗 교환	`[2, 1, 3, 5, 8]`	피벗 `3`의 인덱스 2가 최종 위치로 확정

분할 직후 왼쪽의 [2, 1]은 피벗보다 작지만 아직 정렬된 상태가 아니다. 왼쪽 [2, 1]과 오른쪽 [5, 8]을 각각 다시 정렬해야 전체 결과 [1, 2, 3, 5, 8]을 얻는다.

분할 방식에는 여러 변형이 있으므로 같은 피벗을 사용해도 중간 배열은 달라질 수 있다. 추적 문제에서는 피벗 위치, 포인터 이동 방향, 동률 처리 조건을 먼저 확인해야 한다.

복잡도를 결정하는 분할 균형

한 번의 분할은 현재 구간의 원소를 대체로 한 번씩 확인하므로 Θ(n)의 작업이 든다.

피벗이 구간을 비슷한 크기로 나누면 재귀 깊이가 Θ(log n)이 되어 전체가 Θ(n log n)이다.
피벗이 계속 최솟값이나 최댓값이 되면 한쪽 구간의 크기가 매번 n - 1이 되어 Θ(n²)까지 나빠진다.
정렬된 입력에서 첫 원소나 마지막 원소만 피벗으로 고르는 단순 규칙은 편향 분할을 만들 수 있다.
무작위 피벗이나 중앙값에 가까운 피벗 선택은 편향 분할 가능성을 줄이지만, 일반 퀵 정렬의 이론적 최악 Θ(n²)을 없애는 것은 아니다.

표준적인 제자리 퀵 정렬은 멀리 떨어진 원소를 교환할 수 있으므로 같은 키의 상대 순서를 보장하지 않는다.

힙 정렬

힙 정렬(Heap Sort)은 배열을 힙으로 만든 뒤 루트의 최댓값을 반복적으로 꺼내 정렬 완료 구간으로 보낸다. 오름차순 정렬에는 일반적으로 최대 힙(Max Heap)을 사용한다.

최대 힙은 다음 두 조건을 만족한다.

모양 조건: 완전 이진 트리다.
순서 조건: 모든 부모 키가 자식 키보다 크거나 같다.

따라서 루트는 전체 최댓값이지만, 왼쪽 자식과 오른쪽 자식 사이의 순서나 같은 레벨 전체의 정렬 상태는 보장하지 않는다. 힙은 이진 탐색 트리가 아니다.

0부터 시작하는 배열에서 인덱스 i의 관계는 다음과 같다. 부모 공식은 루트가 아닌 노드(i > 0)에 적용한다.

부모: floor((i - 1) / 2)
왼쪽 자식: 2i + 1
오른쪽 자식: 2i + 2

최대 힙 구축과 정렬 구간 추적

입력 [5, 2, 8, 1, 3]을 아래쪽 내부 노드부터 힙 복구(heapify)하면 최대 힙 [8, 3, 5, 1, 2]를 만들 수 있다.

단계	배열 상태	구간의 의미
최대 힙 구축	`[8, 3, 5, 1, 2]`	전체가 힙, 아직 정렬 완료 원소 없음
1회 추출 후	`[5, 3, 2, 1 │ 8]`	`8`이 최종 위치에 확정
2회 추출 후	`[3, 1, 2 │ 5, 8]`	`5, 8`이 정렬 완료
3회 추출 후	`[2, 1 │ 3, 5, 8]`	`3, 5, 8`이 정렬 완료
완료	`[1, 2, 3, 5, 8]`	전체 정렬 완료

표의 │는 설명 편의를 위해 힙 구간과 정렬 완료 구간을 나눈 표시다. 실제 배열에 저장되는 문자는 아니다.

각 추출 단계에서는 다음을 반복한다.

루트와 현재 힙의 마지막 원소를 교환한다.
힙 크기를 1 줄여 방금 보낸 원소를 힙 연산 대상에서 제외하고 정렬 완료 구간에 포함한다.
새 루트부터 더 큰 자식과 비교하며 아래로 내려가 최대 힙을 복구한다.

아래쪽 내부 노드부터 수행하는 표준 상향식 힙 구축(build-heap)은 Θ(n)이다. 모든 원소를 하나씩 삽입하는 비용 n × log n으로 단순 계산하면 안 된다. 힙 구축 뒤에는 n - 1번의 추출과 최대 Θ(log n)의 힙 복구가 이어지므로 전체 정렬은 모든 입력에서 O(n log n)의 상한을 가지며, 일반적으로 평균·최악은 Θ(n log n)이다. 구현 방식과 중복 키 상태에 따라 실제 최선의 비교 횟수는 더 작아질 수 있으므로, 시험 비교표의 O(n log n) 상한과 정확한 Θ 표기를 구분한다.

배열 내부에서 교환하므로 보조 공간은 O(1)이지만, 장거리 교환 때문에 같은 키의 입력 순서를 유지하지 못해 불안정하다.

병합 정렬

4·1·3·2를 4·1과 3·2로 나누고 원소 하나씩 분리한다. 1·4와 2·3으로 병합한 뒤 1·2·3·4를 만든다.

위에서는 구간을 나누고, 아래에서는 이미 정렬된 구간을 작은 값부터 합친다.

병합 정렬(Merge Sort)은 배열을 원소 하나짜리 구간까지 나눈 뒤, 정렬된 두 구간을 하나의 정렬 구간으로 합친다. 퀵 정렬이 “분할은 어렵고 결합은 거의 없는” 방식이라면, 병합 정렬은 “분할은 단순하고 병합에서 실제 정렬이 이루어지는” 방식이다.

입력 [4, 1, 3, 2]를 나누어 [1, 4]와 [2, 3]으로 각각 정렬한 뒤 다음처럼 병합한다.

두 구간의 첫 값 1과 2를 비교하여 1을 옮긴다.
남은 첫 값 4와 2를 비교하여 2를 옮긴다.
4와 3을 비교하여 3을 옮긴다.
오른쪽 구간이 비었으므로 왼쪽의 4를 붙여 [1, 2, 3, 4]를 완성한다.

병합 대상 두 구간은 각각 이미 정렬되어 있어야 한다. 한쪽을 다 사용하면 다른 쪽의 남은 원소는 비교 없이 그대로 붙일 수 있다.

안정성과 보조 공간

동일한 키가 왼쪽과 오른쪽 구간의 맨 앞에 동시에 나타나면 왼쪽 원소를 먼저 선택해야 원래의 상대 순서가 유지된다. 예를 들어 왼쪽의 4A가 오른쪽의 4B보다 원래 앞에 있었다면 동률에서 4A를 먼저 옮겨야 안정 정렬이 된다.

표준 배열 병합 정렬은 병합 결과를 임시 배열에 저장하므로 Θ(n)의 보조 공간을 사용한다. 각 재귀 레벨에서 전체 n개 원소를 처리하고 레벨 수가 Θ(log n)이어서 입력 상태와 관계없이 Θ(n log n)이다. 순차적으로 읽으며 병합하기 쉬워 주기억장치보다 큰 데이터를 다루는 외부 정렬에도 활용된다.

기수 정렬

기수 정렬(Radix Sort)은 원소끼리 직접 대소를 비교하지 않고 키를 자릿수나 문자 위치로 나누어 처리하는 분배 정렬이다. 여기서는 시험에서 자주 추적하는 LSD(Least Significant Digit) 방식을 다룬다.

LSD 방식은 가장 낮은 자릿수부터 시작해 높은 자릿수로 이동한다. 10진수 정수라면 일의 자리, 십의 자리, 백의 자리 순서다. 자릿수가 짧은 수는 앞쪽에 0이 있다고 보고 처리한다. 예를 들어 2는 세 자리 기준으로 002와 같다.

입력 [170, 45, 75, 90, 802, 24, 2, 66]을 10진수 LSD 방식으로 정렬하면 다음과 같다.

처리 자릿수	안정적으로 수집한 결과	보장되는 순서
일의 자리	`[170, 90, 802, 2, 24, 45, 75, 66]`	일의 자리 기준
십의 자리	`[802, 2, 24, 45, 66, 170, 75, 90]`	십의 자리와 일의 자리 기준
백의 자리	`[2, 24, 45, 66, 75, 90, 170, 802]`	전체 오름차순 완료

같은 버킷에 들어온 원소는 들어온 순서대로 꺼내야 한다. 일의 자리가 같은 170과 90, 802와 2, 45와 75의 상대 순서를 보존해야 다음 자릿수 처리 뒤에도 낮은 자릿수 순서가 남는다. 따라서 LSD 기수 정렬의 각 자릿수 단계에는 안정 정렬이 필요하다.

원소 수를 n, 처리할 자릿수 수를 d, 각 자릿수가 가질 수 있는 값의 수를 k라고 하면 한 자릿수의 분배·수집은 대표적으로 Θ(n+k), 전체는 Θ(d(n+k))이다. 10진수에서는 k가 10이다. 대표적인 버킷 또는 계수 배열 구현은 Θ(n+k)의 보조 공간을 사용한다.

기수 정렬의 성능은 키가 자릿수로 나뉘고 d와 k가 적절하다는 전제에 의존한다. 음수, 소수, 가변 길이 문자열은 부호와 길이를 처리할 별도 규칙이 필요하므로 추가 조건 없이 같은 추적 절차를 적용하면 안 된다. 기수 정렬은 비교 정렬이 아니므로 비교 기반 정렬의 Ω(n log n) 하한을 그대로 적용하지 않는다.