자연계열 2번

(알고리즘 1)스텝 1. $\displaystyle a_1$에 새로 이름을 주어 $\displaystyle b_1$이라고 하자.스텝 2. $\displaystyle a_1,\ldots,a_k$를 증가하는 순서대로 정리하여 $\displaystyle b_1,\ldots,b_k$라고 부르기로 하자. $\displaystyle a_{k+1}$을 이미 정리되어 있는 $\displaystyle b_1,\ldots,b_k$와 비교하여 정리하려고 한다. 이를 위하여 $\displaystyle a_{k+1}$을 기존 $\displaystyle b_1,\ldots,b_k$의 작은 숫자부터 차례로 비교하여 $\displaystyle a_{k+1}$이 들어가야 할 위치를 알아내고 그 위치에 $\displaystyle a_{k+1}$를 집어넣는다.스텝 3. 스텝 2를 반복하여 $\displaystyle a_1,\ldots,a_n$이 정리되면, 알고리즘을 종료한다.

(알고리즘 2)스텝 1. $\displaystyle a_1$에 새로 이름을 주어 $\displaystyle b_1$이라고 하자.스텝 2. $\displaystyle a_1,\ldots,a_k$를 증가하는 순서대로 정리하여 $\displaystyle b_1,\ldots,b_k$라고 부르기로 하자. $\displaystyle a_{k+1}$을 이미 정리되어 있는 $\displaystyle b_1,\ldots,b_k$와 비교하여 정리하려고 한다.스텝 2-A. $\displaystyle b_1,\ldots,b_k$ 중 가운데 배치되어있는 $\displaystyle b_{[(k+1)/2]}$와 $\displaystyle a_{k+1}$을 비교하여, $\displaystyle a_{k+1}$이 $\displaystyle b_{[(k+1)/2]}$보다 작으면 $\displaystyle a_{k+1}$을 $\displaystyle b_{[(k+1)/2]}$의 왼쪽에 배치하고 반대의 경우 오른쪽에 배치한다.스텝 2-B. $\displaystyle a_{k+1}$이 $\displaystyle b_l$보다 크고 $\displaystyle b_{l+m+1}$보다 작다고 하자. 이제 $\displaystyle a_{k+1}$을 $\displaystyle b_l$와 $\displaystyle b_{l+m+1}$사이에 배치되어있는 $\displaystyle b_{l+1},\ldots,b_{l+m}$와 비교하여 정리하려고 한다. $\displaystyle b_{l+1},\ldots,b_{l+m}$ 중 가운데 배치되어있는 $\displaystyle b_{l+[(m+1)/2]}$와 $\displaystyle a_{k+1}$을 비교하여, $\displaystyle a_{k+1}$이 $\displaystyle b_{l+[(m+1)/2]}$보다 작으면 $\displaystyle a_{k+1}$을 $\displaystyle b_{l+[(m+1)/2]}$의 왼쪽에 배치하고 반대의 경우에는 오른쪽에 배치한다.스텝 2-C. 스텝 2-B를 반복하여 $\displaystyle a_1,\ldots,a_{k+1}$이 정리되면, 스텝 2를 종료한다.스텝 3. 스텝 2를 반복하여 $\displaystyle a_1,\ldots,a_n$이 정리되면, 알고리즘을 종료한다.