Sort Algorithm

최근 정렬알고리즘을 공부하면서 STL의 함수와 내가 구현한 알고리즘의 엄청난 속도차이를 느꼈다.
결론부터 말하자면 STL의 알고리즘을 분석하고 나만의 HSort를 구현하는 것이 목표이다.
HSort구현에 앞서 기존의 알고리즘들을 구현해보고 비교 분석해보았다. 
결과는 아래와 같다.(오름차순 정렬을 기준으로 비교하였다.)

전체 크기	100,000
초기 상태	난수	역순	이미 정렬된 상태
Insertion Sort	10.60	18.70	0.00056
Bubble Sort	33.80	22.30	17.60
Selection Sort	31.60	19.13	13.20
Shell Sort	0.036	0.012	0.0074
Quick Sort_ver_1	0.017	12.89	13.21
Quick Sort_ver_2	0.017	0.0076	0.0072
Quick Sort_ver_3	0.018	25.05	37.21
STL::qsort	0.019	0.005	0.0008
STL::sort	0.021	0.0031	0.002
STL::stable_sort	0.05	0.07	0.01

전체 크기	100,000,000
초기 상태	난수	역순	이미 정렬된 상태
Shell Sort	105	17	13.6
Quick Sort_ver_1	23	( 너무 오래걸림 )	( 너무 오래걸림 )
Quick Sort_ver_2	25	8.98	8.46
Quick Sort_ver_3	32	( 너무 오래걸림 )	( 너무 오래걸림 )
STL::qsort	4.40	24.20	0.89
STL::sort	0.28	8.30	1.02
STL::stable_sort	63.01	57.23	20.57

각각의 구현된 알고리즘 및 분석 내용은 링크를 걸겠다.

추가

2015/12/28 - 비주얼스튜디오에서는 실행시간이 많이 차이난다. 특히 <algorithm>의 sort는 함수 구현이 완전 다른듯 하다. 이유는 모르겠다. 참고로 위의 시간은 맥OS의 Xcode에서 실행한 결과이다. 윈도우에서 전반적으로 시간이 느려졌으니 내컴퓨터의 성능 문제라고 할수 있겠지만 stl qsort의 경우 오히려 10, 10, 9의 시간으로 역순일때 더빠른 속도를 냈기 때문에 STL함수는 구현이 다르다고 할수 있을 것 같다.