Sorting Algorithm efficiency

데이터 구조 과제로 sorting algorithm efficiency를 구하고 있는데,

하면 할 수록, 예상외의 결과가 나와서 그저 깜놀하고 있다.

일단
straight insertion sort, selection sort, bubble sort는 정말로 성능의 차이가 거의 없다.
충실하게 1/2 * n^2 + 1/2 * n을 만족하고 있다는 느낌...

<straight insertion sort, selection sort, bubble sort efficiency>
















Shell Sort는 계산을 안해봐서 모르겠고...

Heap Sort하고 Quick Sort의 차이가 의외로 충격적이었다.
분명 Heap Sort하고 Quick Sort 둘 다 Big O 값은 n * log(n)을 만족한다.

그런데 Quick Sort가 Heap Sort보다 2배 가량 더 빠르다...!!!
loop 반복 횟수도 절반이다...

이...이거 뭐지?!

분명 F(n)값을 계산하봐도 Heap Sort나 Quick Sort 모두 성능에는 큰 차이가 없는걸로 나타난다...
왜!!! 왜!!! Quick Sort는 넘사벽인것이냐... ...!!!!

<Heap Sort Efficiency>
















<Quick Sort efficiency>

















진짜... Quick Sort가 진리이긴 진리인가보다... 그냥 온 몸에 전율이... ..

-------------------------------<내용 추가 -2011년 6월 9일>-------------------------------

Quick Sort가 왜 Heap Sort보다 좋은지 몰라서 한참 고민하고 있었는데
최근 들어서 그 이유를 깨달았다.

Heap Sort는 Tree를 이용하기 때문에 밑이 2인 로그를 취한다.
반면 Quick Sort는 평균적으로 밑이 e인 자연로그이다.

Big-O값은 둘 다 n*log(n)으로 같지만, Big-O는 로그의 밑을 신경 안쓰기 때문에 그런거지...
실질적인 효율은 Quick Sort가 더 좋은 것이다.

우왕 Quick Sort 찬양