| r8 ➤ r9 |
| 10 | ====정렬 의사 코드==== |
| 11 | 다음은 선택 정렬의 의미를 간이화하여 서술한 코드이다. |
| 38 | ====정렬 의사 코드 ==== |
| 64 | ====정렬 의사 코드==== |
| 94 | ====정렬 의사 코드==== |
| 132 | ====정렬 의사 코드==== |
| 181 | 힙 자료구조를 이용해 데이터를 정렬하는 알고리즘으로, 배열을 최대 힙(또는 최소 힙)으로 만든 뒤, 루트(가장 크거나 작은 값)를 배열의 마지막 요소와 교환하고 힙 크기를 줄이는 과정을 반복하는 알고리즘이다. 본 문서에서는 가장 큰 원소 맨 위의 노드에 삽입하는 것을 기준으로 서술한다. |
| 182 | |
| 183 | 우선 힙이 무엇인지 정확히 알아보자. 1) 완전 이진 트리 구조를 사용하며 2) 모든 노드는 값을 갖고, 그것은 자식 노드(들) 값보다 크거나 같다. |
| 184 | 완전 이진 트리 구조의 경우 논리적으로는 트리지만, 구현은 배열로 한다. 맨 위의 노드에서 차례로 내려가며 왼쪽에서 오른쪽으로 A[0], A[1], … A[n]이라고 할 수 있다. A[k]의 자식은 A[2k+1], A[2k+2]이며 부모는 A[⌊(k-1)/2⌋]이다. 이를 이용하여 완전 이진 트리를 힙으로 바꿀 수 있는데, 이를 '스며내리기'라고 한다. 스며내리기는 자식이 존재하는 가장 밑의 노드부터 차근차근 올라오며, 노드가 자식보다 작으면 자식과 교환한다. |
| 185 | |
| 186 | 힙 정렬은 힙에서 루트에 위치한 최대 원소를 제거한 뒤, 스며내리기 연산을 통해 힙 특성을 복구하고, 이렇게 얻은 최대 원소를 배열의 뒤쪽부터 차례로 저장해 나가는 방식의 정렬이다. |
| 187 | ====힙 만들기 의사코드==== |
| 188 | 다음은 스며내리기를 하는 과정을 서술한 코드이다. |
| 189 | |
| 190 | {{{#!syntax java |
| 191 | percolateDown(A[], k): |
| 192 | child ← 2k+1 |
| 193 | right ← 2k+2 |
| 194 | if (child ≤ n-1) |
| 195 | if (right ≤ n-1 and A[child] < A[right]) |
| 196 | child ← right |
| 197 | if (A[k] < A[child]) |
| 198 | A[k] ↔ A[child] |
| 199 | percolateDown(A, child) |
| 200 | }}} |
| 201 | 다음은 배열 A[0…n-1]을 힙으로 만드는 과정을 서술한 코드이다. |
| 202 | |
| 203 | {{{#!syntax java |
| 204 | buildHeap(A[]): |
| 205 | for i ← (n-2)/2 downto 0 |
| 206 | percolateDown(A, i) |
| 207 | }}} |
| 208 | 다음은 힙에서 원소를 삭제하는 과정을 서술한 코드이다. 힙에서 최대 원소를 리턴하고 삭제하여 힙의 크기를 하나 줄인다. 이 방법은 맨 위의 노드를 최소 원소로 대체한 뒤 스며내리기하는 과정으로 이루어진다. |
| 209 | |
| 210 | {{{#!syntax java |
| 211 | deleteMax(A[]): |
| 212 | max ← A[0] |
| 213 | A[0] ← A[n-1] |
| 214 | n-- |
| 215 | percolateDown(A,0) |
| 216 | return Max |
| 217 | }}} |
| 218 | ====정렬 의사 코드==== |
| 219 | 다음은 힙 정렬을 서술한 코드이다. 앞에서 힙을 만드느라 고생한 덕으로, 힙 정렬의 의사 코드는 의미 파악이 어렵지 않다. |
| 220 | |
| 221 | {{{#!syntax java |
| 222 | heapSort(A[]): |
| 223 | buildHeap() |
| 224 | for i ← n-1 downto 1 |
| 225 | A[i] ← deleteMax(A) |
| 226 | }}} |
| 227 | ====분석==== |
| 228 | heapSort의 for 루프는 n-1번 순환하고, 각 순환에서 시간을 좌우하는 deleteMax()는 충분히 잡아도 [math(O(\log n))]이다. 힙 구성을 담당하는 buildHeap()에 소요되는 시간은 [math(\Theta(n))]이다. (이는 하위 문단에 자세히 서술한다.) 그러므로 힙 정렬의 총 수행 시간은 [math(O(n\log n))]이고, 힙 정렬은 비교 기반 정렬이므로 [math(\Theta(n\log n))]가 된다. |
| 229 | =====힙 구성의 증명===== |
| 230 | percolateDown()은 해당 서브 트리의 높이가 시간을 좌우하는데, 어떤 서브 트리도 높이가 [math(\log_{2} n)]을 넘지 않으므로 percolateDown()을 한번 수행하는데 [math(O(\log n))]이 소요된다. buildHeap()에서 percolateDown()을 호출하는 횟수는 ⌊n/2⌋이므로 전체적으로 --단순하게 곱한다면-- [math(O(n\log n))]이 된다. 그러나 모든 percolateDown()의 시간을 [math(O(\log n))]으로 잡은 것은 다소 지나치다. 맨 처음 호출되는 percolateDown()의 입력 트리는 고작 한 단계의 작업만 하면 되는데, 이런 것들이 꽤 여러 개 있다. 위로 올라갈수록 높이가 높은 서브 트리의 수는 줄어든다. 이 경우의 수들을 합산하면 [math(O(n\log n))]가 아닌 [math(\Theta(n))]이 된다. 이것을 자세히 증명해보자. |
| 231 | |
| 232 | percolateDown()은 힙의 높이에 비례하는 시간이 소요된다. 즉, 힙의 높이가 h라면 [math(O(h))]의 시간이 소요된다. 원소의 수가 총 [math(n)]인 힙의 높이는 [math(\log_{2} n)]이다. 높이가 [math(h)]인 트리의 노드 수는 기껏해야 [math(⌈\frac{n}{2^{h+1}}⌉)]이다. 따라서 buildHeap()의 수행 시간은 다음과 같다. |
| 233 | |
| 234 | [math(\sum_{h=0}^ {⌊\log_{2} n⌋} ⌈\frac{n}{2^{h+1}}⌉O(h)=O(n \sum_{h=0}^ {⌊\log_{2} n⌋} \frac{h}{2^{h+1}})=O(n))] |
| 235 | |
| 236 | 마지막 단계는 [math(\sum_{h=0}^ {⌊\log_{2} n⌋} \frac{h}{2^{h+1}})]가 2보다 크지 않기 때문이다. 임의의 [math(k)]에 관해 [math(S_{k}=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+…+\frac{k}{2^k})]라 하면 [math(2S_{k}=1+\frac{2}{2^1}+\frac{3}{2^2}+…+\frac{k}{2^{k-1}})]이고 [math(2S_{k}-S_{k}=S_{k}=1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+…+\frac{1}{2^{k-1}}-\frac{k}{2^k} \leq 2 - \frac{k}{2^k} \leq 2)]이다. |
