1. 계산복잡도와 정렬의 하한
•
계산복잡도(computational complexity):
◦
알고리즘의 효율을 시간복잡도, 공간복잡도 기준으로 분석
◦
어떤 문제에 대해, “모든 알고리즘이 달성할 수 있는 최선의 하한(lower bound)”을 결정하는 것이 중요
•
정렬(sorting) 문제의 하한:
◦
비교 기반 정렬의 계산복잡도 하한은 Ω(n log n)
◦
n개의 키를 정렬하는데 이보다 더 빠른 비교 기반 알고리즘은 존재하지 않음이 증명됨
◦
실제로 mergesort, heapsort 등은 Θ(n log n)로 동작
2. 시간복잡도, 공간복잡도, 제자리 정렬
•
시간복잡도(time complexity): 연산의 총 횟수(예: 비교, 할당)로 측정
•
공간복잡도(space complexity): 추가적으로 필요한 메모리(배열 등)의 크기
•
제자리 정렬(in-place sort): 추가 공간 사용 없이(상수 크기 메모리만) 입력 배열 내에서 정렬 수행
3. 주요 정렬 알고리즘 및 분석
3.1 교환정렬 (Exchange Sort)
•
아이디어: 모든 쌍을 비교하여 앞에 큰 값이 있으면 자리 교환
•
알고리즘:
for (i = 1; i <= n-1; i++)
for (j = i+1; j <= n; j++)
if (S[j] < S[i])
exchange S[i] and S[j];
C++
복사
•
최악 시간복잡도:
◦
비교: n(n-1)/2 = Θ(n²)
◦
할당(교환): 3 * n(n-1)/2 = Θ(n²)
•
평균:
◦
비교의 1/2에서 교환 발생 → 평균 교환 횟수는 최악의 1/2
•
특징: 제자리 정렬
3.2 삽입정렬 (Insertion Sort)
•
아이디어: 이미 정렬된 배열에 새로운 값을 “삽입”하듯 차례로 키를 끼워넣음
•
알고리즘:
for (i = 2; i <= n; i++) {
x = S[i];
j = i - 1;
while (j > 0 && S[j] > x) {
S[j+1] = S[j];
j--;
}
S[j+1] = x;
}
C++
복사
•
최악 시간복잡도:
◦
비교: (n² - n)/2 = Θ(n²)
◦
할당: (n² - n)/2 = Θ(n²)
•
평균 시간복잡도:
◦
비교, 할당 모두 Θ(n²)
•
특징:
◦
제자리 정렬
◦
“거의 정렬된 데이터”에 대해 매우 빠름(거의 선형)
3.3 선택정렬 (Selection Sort)
•
아이디어: 남아있는 부분에서 최솟값을 찾아 앞에 배치(교환)
•
알고리즘:
for (i = 1; i <= n-1; i++) {
smallest = i;
for (j = i+1; j <= n; j++)
if (S[j] < S[smallest]) smallest = j;
exchange S[i] and S[smallest];
}
C++
복사
•
비교 횟수:
◦
항상 n(n-1)/2 = Θ(n²)
•
할당(교환) 횟수:
◦
n-1회 (각각 3번의 할당) → Θ(n)
•
특징:
◦
제자리 정렬
3.4 거품정렬 (Bubble Sort)
•
아이디어: 인접한 두 원소를 비교하여 큰 값을 뒤로 “버블”처럼 올려보냄. n회 반복
•
알고리즘:
for (i = n; i >= 1; i--)
for (j = 2; j <= i; j++)
if (S[j-1] > S[j])
exchange S[j-1] and S[j];
C++
복사
•
비교:
◦
n(n-1)/2 = Θ(n²)
•
할당(교환):
◦
최악 3n(n-1)/2 = Θ(n²)
•
특징:
◦
제자리 정렬
◦
실제로 가장 비효율적인 알고리즘 중 하나
4. 정렬 알고리즘 시간복잡도/공간복잡도/비교
알고리즘 | 비교횟수 | 할당횟수(교환) | 추가공간 | 특징 |
교환정렬 | Θ(n²) | Θ(n²) | O(1) | 단순, 비효율적 |
삽입정렬 | Θ(n²) | Θ(n²) | O(1) | 거의 정렬시 빠름 |
선택정렬 | Θ(n²) | Θ(n) | O(1) | 교환 가장 적음 |
거품정렬 | Θ(n²) | Θ(n²) | O(1) | 실제로 가장 느림 |
•
모두 비교 기반, 제자리 정렬(in-place)
5. 정렬 하한과 최적 알고리즘의 존재성
•
비교 기반 정렬에서 Ω(n log n)보다 빠른 방법은 이론적으로 불가능(정렬 하한)
•
mergesort, heapsort 등은 이 하한에 도달(Θ(n log n))
•
단, 입력이 제한적이거나 키 값의 범위가 제한적일 때(예: counting sort, radix sort 등)에는 더 빠른 정렬이 가능함
정렬#2
1. 순열에서의 역(Inversion)
•
n개의 원소를 정렬할 때, n!개의 순열이 존재.
•
순열 [k₁, k₂, …, kₙ]에서 역(inversion)이란
i < j이고 kᵢ > kⱼ인 쌍(ki, kj).
•
예: [3, 2, 4, 1, 6, 5]의 역은 (3,2), (3,1), (2,1), (4,1), (6,5), 총 5개.
•
역이 없다는 것은 이미 정렬된 상태.
•
정렬의 본질: 모든 역을 제거하는 과정.
2. 한 번 비교로 최대 하나의 역만 제거하는 알고리즘의 하한
•
정리: 비교만으로 정렬하는 알고리즘에서,
한 번의 비교로 최대 한 개의 역만 제거할 수 있다면
◦
최악의 경우 최소 비교 횟수: n(n–1)/2
◦
평균 최소 비교 횟수: n(n–1)/4
•
증명(최악):
내림차순 [n, n–1,…,2,1]에는 n(n–1)/2개의 역 존재.
각 비교로 한 개의 역만 제거하므로, 최소 n(n–1)/2회 필요.
•
증명(평균):
임의의 순열과 그 전치(transpose)의 역의 개수 합이 n(n–1)/2이므로,
평균적으로 순열 한 개당 n(n–1)/4개의 역이 존재.
•
삽입정렬, 교환정렬, 거품정렬:
한 번 비교로 최대 하나의 역만 제거하므로,
이 하한보다 효율적일 수 없음.
3. 합병정렬의 역 제거
•
합병정렬은 한 번의 비교로 여러 개의 역을 동시에 제거할 수 있음.
•
예: [3, 4], [1, 2]를 합병할 때, 3과 1을 비교하여
(3,1), (4,1) 역 두 개를 동시에 제거.
3과 2 비교 시 (3,2), (4,2)도 동시에 제거.
•
이러한 이유로 합병정렬은 O(n log n) 시간에 모든 역을 제거 가능.
4. 힙정렬(Heapsort)
4.1 힙(heap) 자료구조
•
힙 성질: 어떤 노드의 값은 그 자식 노드들보다 크거나 같다(max heap).
•
Essentially complete binary tree 구조.
•
힙의 연산:
◦
최대값 확인 O(1)
◦
최대값 제거/삽입/변경 O(log n)
•
배열 기반 구현:
◦
Left child: 2i
◦
Right child: 2i+1
◦
Parent: floor(i/2)
4.2 Siftdown 연산
•
힙 속성을 유지하기 위한 조정 연산.
•
부모 키가 자식보다 작으면 자식과 교환, leaf까지 반복.
4.3 heapsort 알고리즘
•
1단계: n개의 키로 힙을 구성(makeheap).
•
2단계: root(최댓값)를 제거, siftdown으로 재구성, 제거 값을 정렬 배열에 저장.
•
3단계: 이 과정을 n–1번 반복하여 오름차순 정렬.
Pseudocode
cpp
CopyEdit
void siftdown(heap& H, index i) { ... }
keytype root(heap& H) { ... }
void removekeys(int n, heap& H, keytype S[]) { ... }
void makeheap(int n, heap& H) { ... }
void heapsort(int n, heap& H, keytype S[]) {
makeheap(n,H);
removekeys(n,H,S);
}
C++
복사
4.4 makeheap 구현 방식
•
방법 1: 데이터 삽입시마다 sift-up으로 힙 성질 유지
◦
sift-up 총 비교 횟수: (n+1)lg n – 2n + 2 ≈ O(n log n)
•
방법 2: 모든 데이터를 트리에 넣은 후, siftdown을 각 서브트리에 적용
◦
siftdown 총 비교 횟수: 2(n–1)
◦
실제 makeheap은 O(n) 시간에 수행 가능
4.5 removekeys 단계
•
siftdown 횟수의 총합: d–2 2ᵈ + 2 = n lg n – 2n + 2 (n=2ᵈ)
•
각 siftdown에서 2회 비교, 전체 비교 횟수는 2n lg n – 4n + 4
•
전체 heapsort의 최악 비교 횟수:
W(n) ≈ 2n lg n (n=2ᵈ, 힙·키의 비교 기준)
4.6 공간복잡도
•
배열로 힙 구현 시 제자리정렬(in-place sort).
•
공간복잡도 Θ(1).
5. 비교 기반 정렬의 하한
•
n개의 서로 다른 키 정렬 문제에 대해
결정트리(decision tree)로 나타낼 수 있음.
•
올바른 알고리즘은 n!개의 리프(각 입력에 대한 정렬 결과)를 갖는 유효한 이진트리를 가짐.
•
결정트리 깊이 d, 리프 m이면 d ≥ ⎡log₂ m⎤.
•
n!개의 리프이므로,
최악의 경우 비교 횟수 하한은 ⎡log₂(n!)⎤.
•
Stirling 근사 사용:
log₂(n!) ≥ n log₂ n – 1.45 n
→ Ω(n log n)이 비교 기반 정렬의 하한.
•
결론: 키 비교만으로는 n log n보다 더 빠른 정렬 불가능.
6. 기수정렬(Radix Sort)
•
키에 “자릿수 정보”가 있을 때, 비교 없이 정렬 가능.
•
d자리의 10진수 키 n개를 정렬:
◦
각 자리마다 0~9로 분배하는 과정을 d번 반복.
•
각 분배는 O(n+k) (k는 자리수, 보통 상수), 전체 O(d(n+k))
•
단위연산은 비교가 아니라 “자리수 분배” 연산.
