| r9 ➤ r10 | |
| 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)]이다. |
| 237 | ===셸 정렬(Shell Sort)=== |
| 238 | 삽입 정렬의 단점을 보완한 알고리즘으로, 처음에는 큰 간격으로 데이터를 나눠 부분 정렬을 하고, 간격을 점점 줄여가며 최종적으로는 전체 데이터를 효율적으로 정렬하는 알고리즘이다. |
