CH04 : Sorting 5 - Radix Sort

Radix Sort(기수정렬)은 입력의 제한사항으로 인해 문제의 복잡도가 $\Omega (n)$으로 내려간 경우의 정렬 알고리즘이다. (원래 정렬문제 복잡도는 $\Omega (n \log n)$) → Radix Sort는 특수한 상황에서 정렬을 $O(n)$ time에 수행하는 정렬 알고리즘이다.Radix Sort의 Input 기존 정렬 문제와 달리, radix sort 상황에선 다음과 같은 input에 대한 추가 정보가 주어진다.key값은 1부터 임의의 정수 m 사이의 정수이다.key값의 자릿수가 제한돼 있다. (ex. key값은 다섯자리 이하 정수)각 자릿수의 값 범위가 제한적이어야 한다. (ex. 10진수 → 자릿수당 가능한 값 10개(0~9)) 즉, radix sort는 '자릿수 기반으로 정렬 가능..

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)..