| r10 ➤ r11 |
| 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 | |
| 238 | ===스탈린 정렬(stalin sort)=== |
| 239 | 시간복잡도가 [math(O(n))]인 GOAT 알고리즘으로, 배열을 처음부터 뒤로 읽어가면서 뒤쪽이 앞쪽보다 크면 제거하는 것을 반복해 순서대로 정렬된 배열을 얻는다. |
| 240 | ====스탈린 정렬 의사코드==== |
| 241 | {{{#!syntax java |
| 242 | FUNCTION stalinSort(A : list OF sortable items) |
| 243 | n := length(A) |
| 244 | bigger := 0 |
| 245 | B SET empty list |
| 246 | |
| 247 | FOR i := 0 TO n NOT inclusive DO |
| 248 | IF A[i] >= bigger THEN |
| 249 | bigger := A[i] |
| 250 | B.push(A[i]) |
| 251 | END IF |
| 252 | END FOR |
| 253 | |
| 254 | RETURN B |
| 255 | END FUNCTION |
| 256 | }}} |
| 257 | ===타노스 정렬(thanos sort)=== |
| 258 | 스탈린 정렬과 같이 시간복잡도가 [math(O(n))]인 GOAT 알고리즘으로, 배열 요소의 절반을 제거하여 남은 요소가 정렬될 때까지 반복해 정렬된 배열을 얻는다. |
| 259 | ====타노스 정렬 의사코드==== |
| 260 | 누군가가 적어주겠지 |
