CH04 : Sorting 4 - Accelerated Heap Sort

기존 heap sort는 $W(n) = 2n \log n + O(n)$ time이 걸린다. Acclerated heap sort의 경우 이를 $n \log n$으로 단축시킬 수 있다. (2배 speedup) fixHeap을 fixHeapFast로 개선한다. Acclerated Heap Sort아이디어 binary search에선 중앙값과 K의 비교를 통해 앞으로 살펴볼 영역의 절반을 없앤다. 즉 수평적으로 divide and conquer 전략을 사용한다. acclerated heap sort에선 수직적으로 divide and conquer 전략을 사용한다.전략 현재 heap의 height h에 대하여, $\frac {h}{2}$가 될 때까지 vacant의 위치를 내린다.현재 vacant의 key값과 부..

Heap Heap의 조건 Heap이 되기 위한 조건은 다음의 두 개이다.구조조건 : complete binary treeheight h에 대하여, h-1까지는 complete tree (꽉 찬 트리)모든 leaves는 depth h나 h-1에 위치, depth h의 leaves는 왼쪽부터 채워진다.순서조건 : partial order tree propertymaxheap 기준, parent의 key 값이 나보다 크거나 같아야 한다. minheap일 땐 parent의 key 값이 나보다 작거나 같아야 한다.  아래는 heap인지, 아닌지를 구분하는 예시이다.Heap ADT 삽입 : insert()삭제 : deleteMax()*max heap 기준탐색 : getMax()*max heap 기준W(n)$O( \..

Merge sort는 sorting(정렬) 문제의 optimal 알고리즘으로, $O \left(n \log n\right)$ time을 필요로 한다.Merge에 대하여 - 정렬된 sequences의 mergeMerge 문제 오름차순으로 정렬된 sequence A, B에 대하여, A, B를 합하여 하나의 정렬된 sequence C를 만들어라. 전략 A의 첫 원소와 B의 첫 원소 중 최솟값으로 C의 첫 원소를 구한다. 이가 A의 원소였다고 가정하자. 그럼 문제는 A의 나머지 원소와 B의 원소를 merge하는 것으로 재정의된다.  만약 A 혹은 B가 empty하다면, 남은 배열의 원소들을 C의 뒷부분에 붙인다. Algorithm & Analysis Algorithmmerge(A, B, C)//A or B가 e..

정렬 문제에서의 Optimal SolutionUnsorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( n \right)$를 필요로 한다. Sorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( \log n \right)$를 필요로 한다. 즉, input의 형태에 따라 문제의 복잡도는 변화한다.Insertion Sort (삽입정렬)Strategy n개의 원소를 가진 배열에 대하여 index 1부터 n-1의 원소까지가 삽입되듯이 동작한다. 삽입된 해당 원소가 swap을 이용해 적절한 위치로 이동한다. Example회색 영역은 정렬된 원소들, 검은색 영역은 현재 삽입되어 정렬될 원소,..

Abstract Data Type (ADT)ADT란 추상자료형으로, C++의 class와 비슷한 개념이다. ADT 동작과 그 설명을 기반으로 알고리즘을 설계하고, 정확성을 증명한다.ADT를 정의하기 위해선 다음의 것들을 명시해야 한다.자료구조가 저장할 데이터 명시ex. queue면 front, near 등지원하는 함수 명시ex. insert, delete 등동작 설명what은 설명하고, how는 설명하지 않는다. 즉 무엇을 수행하는지는 설명하지만, 어떻게 수행되는지는 설명하지 않는다.error 처리 명시TreeTree 용어root [루트] : 트리의 최상위 노드. 부모가 없는 노드라고도 한다.node의 degree [차수] : 자식의 수. 비어있지 않은 subtree의 수라고도 한다.external no..

문제 정의1. input : 오름차순으로 정렬된 n개의 원소를 가진 배열 E, 값 K2. output : E에 K가 존재할 경우 K의 index, 그 외의 경우 -1해결책 AStrategy A모든 원소를 순차적으로 확인한다.Algorithm Aint seqSearch(int[] E, int n, int K)int ans, idx;ans = -1; //Assume Failurefor (idx = 0; idx Analysis AWorst Case$W(n) = n$ 발생조건 : 배열의 마지막 원소만 K이거나, K가 배열에 없는 경우Average Case$A(n) = q\cdot \frac {n+1}{2} + (1-q)n$ $A(n) = Pr(succ)A_{succ}(n) + Pr(fail)A_{fail}(n)..