[알고리즘] 7장. Sorting

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 7-1

* 계산복잡도(Computational Complexity)
- 얼마나 많은 계산을 해야지 문제가 풀릴 것인가

* 알고리즘의 분석
- 어떤 특정 알고리즘의 효율(efficiency)을 측정
- 시간복잡도(time complexity)
- 공간복잡도(space/memory complexity)

* 문제풀이 접근하는 2가지 방법
- 문제를 푸는 더 효율적인 알고리즘을 개발
- 더 효율적인 알고리즘 개발이 불가능함을 증명

* 문제의 분석
- 일반적으로 "계산복잡도 분석"이란 "문제의 분석"을 지칭
- 어떤 문제에 대해서 그 문제를 풀 수 있는 모든 알고리즘의 효율의 하한(lower-bound)을 결정한다.
- 복잡도 하한이 Ω(f(n))인 문제에 대해서 복잡도가 Θ(f(n))인 알고리즘을 만들어 내는 것이 목표다.

* 정렬문제(sorting) : Ω(nlgn)
- 교환정렬(Exchange sort) : Θ(n^2)
- 합병정렬(Merge sort) : Θ(nlgn)

* 안정성(Stability)
- 같은 키값을 갖는 데이터 간의 정렬 전 순서가 정렬 후에도 유지되는 성질

 

* stable
- 삽입정렬 (insertion sort)
- 합병정렬 (merge sort)
- 거품정렬 (bubble sort)

 

* not stable
- 빠른정렬 (quick sort)
- 힙정렬 (heap sort)
- 선택정렬 (selection sort)
- 교환정렬 (exchange sort)

---

📌 7-2

* <A> 삽입정렬 (Insertion Sort)

void insertionsort(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;
	}
}

* <A> 선택정렬 (Selection Sort)

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];
	}
}

* <A> 교환정렬 (Exchange Sort)

void exchangesort(int n, keytype S[]) {
	index i, j;
	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]
}

* <A> 거품정렬 (Bubble Sort)

void bubblesort(int n, keytype S[]) {
	index i, j;
	for (i=n; i>=1; i--)
		for (j=2; j<=i; j++)
			if (S[j-1] > S[j])
				exchange S[j-1] amd S[j]
}

* Θ(n^2) 알고리즘 비교

	비교횟수	지정횟수
삽입정렬	W(n)=n^2/2 A(n)=n^2/4	W(n)=n^2/2 A(n)=n^2/4
선택정렬	T(n)=n^2/2	T(n)=3n
교환정렬	T(n)=n^2/2	W(n)=3n^2/2 A(n)=3n^2/4
거품정렬	T(n)=n^2/2	W(n)=3n^2/2 A(n)=3n^2/4

* 정렬 알고리즘 비교
- 삽입정렬은 어느정도 정렬된 데이터에 대해서는 빠르게 수행된다.
- 삽입정렬은 교환정렬 보다는 항상 최소한 빠르게 수행된다고 할 수 있다.
- 선택정렬이 교환정렬 보다 일반적으로 빠르다.
- 입력이 이미 정렬되어 있는 경우, 선택정렬은 지정이 이루어지지만(자신의 위치에서) 교환정렬은 지정이 이루어지지 않으므로 교환정렬이 빠르다.
- n의 크기가 크고, 키의 크기가 큰 자료구조일 때는 지정하는 시간이 많이 걸리므로 선택정렬 알고리즘이 삽입정렬 알고리즘보다 더 빠르다.

---

📌 7-3

* 한번 비교하는데 최대한 하나의 역을 제거하는 알고리즘의 하한선
- 역 : 순서쌍 중에 앞에있는 것이 뒤에있는 것보다 큰 상태

* 합병정렬은 비교마다 하나 이상의 역을 제거하므로 교환, 삽입, 선택 정렬보다 효율적이다.

* <A> 빠른정렬 (Quick Sort)

void quicksort(index low, index high) {
	index pivotpoint;
	if (high > low) {
		partition(low, high, pivotpoint);
		quicksort(low, pivotpoint - 1);
		quicksort(pivotpoint + 1, high);
	}
}

---

📌 7-4

* binary tree의 종류
- 완전이진트리(complete(perfect) binary tree)
- 실질적인 완전이진트리(essentially complete binary tree)
- full binary tree(proper binary tree or 2-tree)

* 힙 (heap)
- 힙의 성질(heap property) : 어떤 마디에 저장된 값은 그 마디의 자식마디에 저장된 값보다 크거나 같다. - max heap
- 힙(heap) : 힙의 성질을 만족하는 실질적인 완전이진트리

* 힙 구조의 특성
- 최대값 확인 - O(1)
- 최대값 제거 및 재구성 - O(lg n)
- 데이터 추가, 삭제, 변경 - O(lg n)
- 최대값을 항상 유지해야하는 Queue를 구현하는데 적합하다. - priority queue

* <A> Siftdown
- 힙 성질을 만족하도록 재구성하는 방법. sift: 채로 치다.

void siftdown(heap& H) {
	node parent, largerchild;
	parent = root of H;
	largerchild = parent's child containing larger key;
	while(key at parent is smaller than key at largerchild) {
		exchange key at parent and key at largerchild;
		parent = largerchild;
		largerchild = parent's child containing larger key;
	}
}

- 루트에서 키를 추출하고 힙 성질을 회복하는 의사코드
keytype root(heap& H) {
	keytype keyout;
	keyout = key at the root;
	move the key at the bottom node to the root;
	delete the bottom node;
	siftdown(H);
	return keyout;
}

* <A> 힙정렬 (Heap Sort)
1. n개의 키를 이용하여 힙을 구성한다.
2. 루트에 있는 제일 큰 값을 제거한다. -> 힙 재구성
3. step2를 n-1번 반복한다.

void heapsort(int n, heap H, keytype S[]) {
	makeheap(n, H);
	removekeys(n, H, S);
}

void makeheap(int n, heap& H) {
	index i;
	heap Hsub;
	for (i = d - 1; i >= 0; i--)
		for (all subtree Hsub whose roots have depth i)
			siftdown(Hsub);
}

void removekeys(int n, heap H, keytype S[]) {
	index i;
	for (i = n; i >= 1; i--)
		S[i] = root(H);
}

* make heap 방법
- 방법 1 : 데이터가 입력되는 순서대로 heap을 매번 구성
- 방법 2 : 모든 데이터를 트리에 넣은 상태에서 heap 구성

* Θ(nlgn) 알고리즘 비교

	비교횟수	지정횟수	저장공간
합병정렬	W(n)=A(n)=nlgn	T(n)=2nlgn	Θ(n)
빠른정렬	W(n)=n^2/2 A(n)=1.38nlgn	A(n)=0.69nlgn	Θ(lgn)
힙정렬	W(n)=A(n)=2nlgn	W(n)=A(n)=nlgn	Θ(1)

---

📌 7-5

* 키의 비교만으로 정렬하는 경우 하한
- 정렬알고리즘에 대한 결정트리(decision tree)

* 가지친 결정트리(pruned decision tree)

- 일관성 있는 순서로 결정을 내림으로써 뿌리마디로부터 모든 잎마디에 도달할 수 있는 경우, 가지친(pruned) 결정트리다.

* 정리 7.3

- n개의 서로 다른 키를 비교함으로써 만 정렬하는 결정적 알고리즘은 최악의 경우 최소한 「nlgn - 1.45nㄱ번의 비교를 수행한다.

* 키 값의 비교를 통한 정렬은 Ω(nlgn)의 복잡도를 갖는다. 즉, nlgn보다 더 빠른 알고리즘을 개발할 수는 없다.
* 합병정렬의 평균의 경우 성능인 nlgn - 1.26n은 키를 비교만 하여 정렬하는 알고리즘으로는 거의 최적이다.

---

📌 7-6

* <A> 기수정렬 (Radix Sort)
- 분배에 의한 정렬
- 키에 대해서 아무런 정보가 없는 경우 : 불가능
- 키에 대한 어느 정도의 정보를 알고 있는 경우 : 기수(radix, base)를 사용한다.

void radixsort(node_pointer& masterlist, int numdigits) {
	index i;
	node_pointer list[0..9];
	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의 끝에 링크
}

* Topological Sort
- 정의 : i에서 j로 가는 arc가 있을 때 i가 j보다 먼저 오는 정렬 방법

---