Huilife

Heap sort는 heap 자료구조를 기반으로 진행한다. 이 글은 heap 자료구조의 기본 프로시저인 MAX-HEAPIFY, BUILD-MAX-HEAP의 수도코드 및 수행 시간 분석에 대한 이해를 기본으로 한다. heap 자료구조의 기본 프로시저의 수도코드 및 수행 시간 분석은 [Data Structure] Heap에 정리되어 있으므로, 이 페이지에서는 설명을 생략한다. Pseudo Code HEAP-SORT(A) BUILD-MAX-HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A, 1) 수행 시간 분석 BUILD-MAX-HEAP이 $O(n)$ 시간이 걸린다. 여기에 $O..

알고리즘의 수행 시간을 분석하다 보면, 수 많은 점화식들이 쏟아지게 된다. 이를 풀기 위한 방법은 크게 3가지로 나눌 수 있다. 치환법 재귀 트리 방법 마스터 방법 이 포스트에서는 위의 세 가지를 가볍게 핵심만 훑고 지나가 보도록 하자. 추후 시간이 생긴다면 과연 언제 적절한 예시도 추가하도록 하겠다. 치환법 개념 점화식을 풀기 위한 치환법은 다음의 두 단계를 거친다. 해의 모양을 추측한다. 상수들의 값을 알아내기 위해 수학적 귀납법을 사용하고, 그 해가 제대로 동작함을 보인다. 단계 2에서 수학적 귀납법을 사용할 때, 더 작은 문제에 대하여 단계 1에서 추측한 해로 치환한다. 그렇기 때문에 이 방법의 이름이 치환법인 것이다. 재귀 트리 방법 개념 재귀 트리(recursion tree) 방법은 각 노드가..

Merge sort의 특징은 다음과 같다. 외부 정렬 방법이다. 분할 정복을 이용한다. Pseudo Code MERGE 결합 단계에서 정렬된 두 부분 수열을 병합하는 프로시저이다. MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q create L[1, ..., n1 + 1], R[1, ..., n2 + 1] for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = INF R[n2 + 1] = INF i = 1 j = 1 for k = p to r if L[i]

Quick Sort의 특징 내부 정렬을 이용한 방법이다. 분할 정복을 이용한다. 분할 배열 $A[p, ..., r]$ 을 두 개의 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 로 분할한다. 부분 배열 $A[p, ..., q-1]$ 에는 $A[q]$ 보다 작거나 같은 원소를, $A[q+1, ..., r]$ 에는 $A[q]$ 보다 크거나 같은 원소를 배치한다. 정복 quick sort를 재귀 호출해서 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 를 정렬한다. 결합 1, 2의 과정을 통해 부분 배열이 이미 정렬되어 있으므로 따로 합치는 작업이 필요하지 않다. quick sort는 기본적인 quick sort 방법과 랜덤화 기법을 사용하여 모든 입력에..