정렬 문제
🐽 버블 정렬 알고리즘
- 인접한 두 원소를 검사하여 정렬
- 문제: 비내림차순으로 n개의 키 정렬
- 입력: 양의 정수 n, 키의 배열 S[1..n]
- 출력: 비내림차순으로 정렬된 키의 배열 S[1..n]
의사코드
void bubbleSort(int n, keytype &S[]) {
index i, j;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n-i; j++) {
if(S[j] > S[j+1])
swap S[j] and S[j+1];
}
}
}
- 큰 수일 경우 한 칸씩 뒤로
버블 정렬 분석 - 모든 경우
- 단위 연산: 비교
| i | j | 횟수 |
|---|---|---|
| 1 | 1.. | n-1 |
| 2 | 1.. | n-2 |
| … | ||
| n | 1.. | 0 |
- $T(n) = \frac{n(n-1)}{2}$
🐽 삽입 정렬 알고리즘
- 이미 정렬된 배열에 항목을 끼워 넣음으로써 정렬하는 알고리즘
- 문제: 비내림차순으로 n개의 키 정렬
- 입력: 양의 정수 n, 키의 배열 S[1..n]
- 출력: 비내림차순으로 정렬된 키의 배열 S[1..n]
의사코드
void insetionSort(int n, keytype S[]) {
index i, j;
keytype x;
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;
}
}
삽입 정렬 분석 - 최악의 경우
- 기본 연산: 비교
- i가 주어졌을 때, while loop에서 최대 i-1번의 비교 이루어짐
- $W(n) = \sum_{i=2}^{n} (i-1) = \frac{n(n-1)}{2}$
평균의 경우
- i가 주어졌을 때 x가 삽입될 수 있는 장소: i개
| 삽입할 장소의 인덱스 | 비교 횟수 |
|---|---|
| i | 1 |
| i-1 | 2 |
| … | … |
| 2 | i-1 |
| 1 | i-1 |
-
x를 삽입하는데 필요한 비교 횟수
$1\frac{1}{i} + 2\frac{1}{i} + … + (i-1)\frac{1}{i} + (i-1)\frac{1}{i} = \frac{1}{i} \sum_{k=1}^{i-1} k + \frac{i-1}{i} = \frac{(i-1)i}{2i} + \frac{i-1}{i} = \frac{i+1}{2} - \frac{1}{i}$ -
정렬에 필요한 평균 비교 횟수
$\sum_{i=2}^{n} (\frac{i+1}{2} - \frac{1}{i}) ≈ \frac{(n+4)(n-1)}{4} - ln^n ≈ \frac{n^2}{4} ∈ Θ(n^2)$
🐤 교환 정렬 알고리즘
- 문제: n개의 수로 구성된 배열 S 오름차순 정렬
- 입력: 양의 정수 n, 배열 S
- 출력: 오름차순으로 정렬된 배열 S
의사코드
void exchangeSort(int n, number S[]) {
index i, j;
for(i = 1; i <= n; i++) {
for(j = i+1; j <= n; j++)
if(S[j] < S[i]) swap S[i] and S[j];
}
}
swap(index i, j, number &S[]) {
number temp;
temp = S[i];
S[i] = S[j];
S[j] = temp;
}
시간복잡도
- 단위 연산: 조건문 (S[j], S[i] 비교)
- 모든 경우 분석
- j-loop가 수행될 때마다 조건문 1번씩 수행
- 조건문 총 수행 횟수
- i=1, 2, 3, .., n-1 에 따라
- j-loop n-1, n-2, n-3, …, 1 번 수행
- $T(n) = (n-1) + (n-2) + … + 1 = \frac{(n-1)n}{2}$
- 최악의 경우
- 기본 연산: 할당
- 1번 교환하는데 3번 지정
- $W(n) = 3(n-1) + 3(n-2) + … + 3 = \frac{3n(n-1)}{2}$
- 평균의 경우
- 기본 연산: 할당
- i와 j를 비교했을 때 i가 클 확률은 $\frac{1}{2}$, i가 클 때 지정이 발생하므로
- 지정의 횟수: $\frac{3(n-1)}{2}$
- $A(n) = \frac{3(n-1)}{2} + \frac{3(n-2)}{2} + … + \frac{3}{2} = \frac{3n(n-1)}{4}$
🐽 선택 정렬 알고리즘
- 문제: 비내림차순으로 n개의 키 정렬
- 입력: 양의 정수 n, 키의 배열 S[1..n]
- 출력; 비내림차순으로 정렬된 키의 배열 S[1..n]
의사코드
void selectionSort(int n, keytype S[]) {
index i, j, smallest;
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]; // 할당
}
}
exchange(index i, j, number &S[]) {
number temp;
temp = S[i];
S[i] = S[j];
S[j] = temp;
}
선택 정렬 분석 - 모든 경우
- 기본 연산: 비교
| i | 횟수 |
|---|---|
| 1 | n-1 |
| 2 | n-2 |
| … | |
| n-1 | 1 |
- 비교 횟수의 합: $\frac{n(n-1)}{2}$
- $T(n) = \frac{n^2}{2}$
- 기본 연산: 할당
- 1번 교환하는데 3번 지정
- $T(n) = 3(n-1)$
🐽 힙 정렬
최대 힙 Max Heap
- 최대 트리
- 이진 트리에서 각 노드의 키 값이 그 자식 노드보다 큰 트리
- 최대 힙
- 최대 트리이면서 완전 이진 트리
- 최대 트리에서 루트는 가장 큰 키 값을 가짐
- 각 노드의 키 값은 그 노드의 자식 노드에 저장된 값보다 크거나 같음
- 삽입 연산
- 완전 이진 트리의 조건을 만족하기 위해 새 노드는 트리의 마지막 위치에 삽입
- 최대 트리 조건을 만족하기 위해 새 노드는 상위 노드와 반복적으로 비교하여 알맞은 위치 찾음
- 삭제 연산
- 최대 힙에서의 삭제는 루트 노드의 삭제
- 루트 노드를 return
- 가장 마지막 노드를 루트로 가져와서 최대 힙의 특성을 만족하도록 제 위치를 찾아줌
shiftdown
힙 정렬을 위한 데이터 구조
shiftdown: 힙의 특성을 만족하도록 키 값을 아래로 내리는 연산root: 루트 키를 return하고, 바닥 노드를 루트로 옮겨 shiftdown하여 힙을 복원함 (삭제 연산)removekeys: 힙의 키를 정렬된 순서로 배열에 위치시키는 알고리즘makeheap: 본질적으로 완전한 이진 트리를 힙 트리로 구성
shiftdown()
- 힙 구조 특성 만족하도록 구성
void shiftdown(heap& H, index i) { // i는 노드 번호
index parent, largerchild;
keytype shiftkey;
bool spotfound;
shiftkey = H.S[i];
parent = i;
spotfound = false;
while(2*parent <= H.heapsize && !spotfound) { // 자식 노드가 하나라도 있으면
// 자식 노드가 2개라면, 왼쪽/오른쪽 중 어느 자식 노드가 더 큰지 판별
if(2*parent < H.heapsize && H.S[2*parent] < H.S[2*parent+1])
largerchild = 2*parent + 1; // 오른쪽
else largerchild = 2*parent; // 왼쪽
if(shiftkey < H.S[largerchild]) {
H.S[parent] = H.S[largerchild];
parent = largerchild;
}
else spotfound = true;
}
H.S[parent] = shiftkey;
}
struct heap{
keytype S[1..n];
int heapsize;
};
- 자식 노드 index: 적어도 부모 노드의 2배
makeheap()
- 힙 구조 구성
void makeheap(int n, heap& H) {
index i;
H.heapsize = n;
for(i = ⌊n/2⌋; i >= 1; i--)
shiftdown(H, i);
}
root()
- 힙 구조의 루트 값 얻기 & 힙 복원
keytype root(heap& H) {
keytype keyout;
keyout = H.S[1];
H.S[1] = H.S[heapsize]; // 가장 마지막 노드를 루트로
H.heapsize = H.heapsize - 1;
shiftdown(H, 1); // 힙 트리 특성 만족하도록 구성
return keyout;
}
removekeys()
- 정렬
- 힙 구조의 루트를 배열로 이동
void removekeys(int n, heap H, keytype S[]) {
index i;
for(i = n; i >= 1; i--)
S[i] = root(H);
}
힙 정렬 알고리즘
void heapSort(int n, heap& H, keytype S[]) {
makeheap(n, H); // shiftdown()
removeheap(n, H, S); // shiftdown()
}
- makeheap과 removekeys 모두 shiftdown 호출하므로 따로 분석
makeheap 시간복잡도 - 최악의 경우
- 단위 연산: shiftdown 프로시저에서의 키 비교
- $n = 2^k (= 2^d)$라 가정
| depth | node 수 | 키가 shift되는 최대 횟수 |
|---|---|---|
| 0 | $2^0$ | d-1 |
| 1 | $2^1$ | d-2 |
| .. | .. | .. |
| j | $2^j$ | d-j-1 |
| .. | .. | .. |
| d-2 | $2^{d-2}$ | 1 |
| d-1 | $2^{d-1}$ | 0 |
- 최대 횟수의 합
$\sum_{j=0}^{d-1} 2^j (d-j-1)$
= $2^d - d - 1$
- 깊이가 d인 경우 shiftdown 될 횟수의 상한값인 d를 더하면 $2^d - 1$이 됨
- 한 번 shiftdown될 때마다 2번씩 비교
- 실제 비교 횟수: $2(n-1)$
removekeys 시간복잡도 - 최악의 경우
- $n = 2^k (= 2^d)$라 가정
- 총 shift 횟수: $\sum_{j=0}^{d-1} j2^j = nlg^n - 2n + 2$
- 한 번 shift될 때마다 2번씩 비교하므로 실제 비교 횟수: $2nlg^n - 4n + 4$
- 따라서, 최악의 경우: $W(n) ∈ Θ(nlg^n)$
힙 정렬 시간복잡도
- makeheap 시간복잡도 + removekeys 시간복잡도
- 최악의 경우: $W(n) ∈ Θ(nlg^n)$
🐽 기수 정렬 RADIX
- d 개의 숫자로 표현한 k진법 체계의 수를 키로 표현하여 각 숫자에 따라 키를 분배하는 방식
각 키의 가장 왼쪽 숫자부터 기준으로 삼는 경우
오른쪽 숫자부터 분배의 기준으로 삼는 경우
의사코드
void radixsort(node_pointer& masterlist, int numdigits) {
// globally node_pointer list[0.9];
index i;
for(i = 1; i <= numdigits; i++) {
distribute(masterlist, i);
coalesce(masterlist);
}
}
void distribute(node_pointer& masterlist, index i) {
index j;
node_pointer p;
for(j = 0; j <= 9; j++) {
list[j] = NULL;
}
p = masterlist;
while(p != NULL) {
j = p -> key에서 오른쪽으로부터 i번째 숫자값;
p를 list[j]의 끝에 링크;
p = p -> link;
}
}
void coalesce(node_pointer& masterlist) {
index j;
masterlist = NULL;
for(j = 0; j <= 9; j++)
list[j]에 있는 마디들을 masterlist의 끝에 링크;
}
기수 정렬 알고리즘 분석 - 모든 경우
- 단위 연산: 뭉치에 수를 추가하는 연산 (링크 연산)
- 입력 크기: 정렬하는 정수 개수 n, 각 정수를 이루는 digit의 최대 개수 numdigits
- 모든 경우 시간복잡도
$T(n) = numdigits(n + 10) ∈ Θ(numdigits * n)$