찾아봤는데 못찾겠어요..ㅠㅜ :oops: O(N3)라고 예상은 되는데 그렇다면 버블소트 O(N2)보다도 안좋은거같은데요...
http://www.nist.gov/dads/ 온라인 알고리즘 사전입니다. shell은 O(NlogN)이구요. brute로 돌려도 O(N2)이 나오는데 O(N3)가 나올리가 없죠. ^^ 요즘은 intro sort란 놈이 sort계에서 가장 영향력이 있습니다.
shell sort는 insertion sort의 특징인 소팅이 미리 되어있을 수록 linear에 가까운 성능이 나올 수 있다는 점에 착안한 방법입니다.
자세한 분석은 좀 복잡한데.. 대략 http://en.wikipedia.org/wiki/Shell_sort 에 나온대로 N^2보다는 좋은 성능이지요..
NlogN계열보다는 성능이 떨어지지만 그보다 알고리즘이 간단하기때문에 어느정도 갯수 이하의 원소 소팅시 유용하다고 하네요..
검색해보세요.
http://www.nist.gov/dads/
온라인 알고리즘 사전입니다.
shell은 O(NlogN)이구요.
brute로 돌려도 O(N2)이 나오는데 O(N3)가 나올리가 없죠. ^^
요즘은 intro sort란 놈이 sort계에서 가장 영향력이 있습니다.
shell sort는 insertion sort의 특징인 소팅이 미리 되
shell sort는 insertion sort의 특징인 소팅이 미리 되어있을 수록 linear에 가까운 성능이 나올 수 있다는 점에 착안한 방법입니다.
자세한 분석은 좀 복잡한데.. 대략 http://en.wikipedia.org/wiki/Shell_sort
에 나온대로 N^2보다는 좋은 성능이지요..
NlogN계열보다는 성능이 떨어지지만 그보다 알고리즘이 간단하기때문에 어느정도 갯수 이하의 원소 소팅시 유용하다고 하네요..