셸 정렬은 gap이 일정하다는 가정을 하고 있기 때문에 급행-완행으로 그대로 적용하기는 좀 무리가 있죠. 한편 셸 정렬의 gap sequence를 아무리 잘 줘도 O(n log n)이 될 수 없다는 건 이미 알려져 있습니다(Plaxton, Poonen, Suel, 1992). 셸 정렬의 진짜 강점은 삽입 정렬의 장점(거의 정렬된 배열에 대해서 O(n)에 가까워짐)을 살리면서 최악의 경우에도 O(n^2) 시간 복잡도를 피할 수 있다는 것이기도 하고, 병렬 정렬 네트워크에도 적용할 수 있다는 장점도 있습니다(만 이건 병합 정렬도 마찬가지네요).
KTX 탈선 얘기는 듣고 저도 깜짝 놀랐는데 저속 주행 중 사고가 났다는 얘기를 듣고 선로 문제겠구나 했었죠. 큰 사고가 되지 않아서 다행이네요.
후훗, 쉘?셸? 어쨌든 참 신비로운 정렬 알고리즘이죠. 당연히, 현실에서는 모든 역이 동일하게 중요한 구간이 그렇게 길지 않으며, 환승 오버헤드, 선로 용량 등 여러 제약으로 인해, 쉘 정렬의 수열 정하는 전략이 완급 운행 전략에 그대로 적용될 수는 없습니다.
(요즘은 얼굴 보기가 힘들구만..;; 잘 지내고 있으셈? =_=)
-뭐 언제나 제가 남기는 댓글이 그렇지만- OTTD 버젼 중에서 <일단은 오픈소스이니> 승객목적지버젼...이 있습니다. 통상 버전은 승객이던 화물이던간에 A->B 정거장으로 운송하면 그냥 그걸로 끝인, 승객 입장에서 보면 수동적인 시스템이었지만, 승객목적지 버전은 승객이 적극적으로 바뀝니다. A->F로 가야 하면, A->B->C->D->E->F 식으로 환승하는 식.
얼마 전에 했던 세이브파일에서는 <del>귀찮아서</del> 완행밖에 없는 노선을 무더기로 만들었는데, 죄다 포화상태에 걸리더군요-_-. 이 버전은 승객 AI 를 잘 만들어놔서 A->B->C 루트가 포화상태면 A->D->E->F->C 와 같은 우회로도 이용하는 식이라서 포화상태인 노선 옆에 비슷한 방향으로 노선을 또 놨는데도 포화상태가 걸리는 일이 있었습니다. ..... 급행/특급을 깔면 더 나아졌으려나 생각해 봅니다=_=
p.s. 그러고보니 게임이고 하니까 한번은 현실이라면 욕을 더럽게 처먹(...)을만한 노선도 만들어봤습니다. 완행인데, 노선에 고리가 있다고 해야 할까요?. A->B->C->D->E->F->E->C->G->H->I 순서.. (E랑 C가 두번 등장합니다 -_-;;;) (실제로도 효율이 떨어지더군요. C역에서 손님이 죄다 환승하는바람에 그곳에서 열차가 움직이질 못하는..)
승객의 평균적인 이동 시간을 줄이고, 급행 환승 시간 오버헤드와 급행 시간 만회 사이에서 가장 좋은 tradeoff를 낼 수 있는 급행 운행 전략에 대해 체계적인 연구가 필요함을 느낍니다.
조금만 더 조건을 구체적으로 엄밀하게 주고 나면 정보 올림피아드 문제감으로도, 심지어 논문감도 될 수 있을 것 같은데요? ^^