북스카이's 컴퓨터의 백과사전

대문 by 북스카이

2011/12/31 23:59
comsky.egloos.com/4894814
0 comments

만들기 귀찮아서 안 만들고 있던 대문이 생겨버렸습니다.

랄까 대문이라고 해봤자 별거 없네요.

본디 booksky.egloos.com이었던 본 블로그는 오늘부로 comsky.egloos.com으로 변경되고,

booksky.egloos.com에 새로운 식민지를 개설하게 되었습니다.

본 블로그는, 컴퓨터만을 전문적으로 다루게 될 블로그입니다.

그런고로, 컴퓨터와 관련된 내용이 아닌 블로그는 식민지 블로그로 이사를 가게 되었습니다.

booksky.egloos.com <- 본격 취미 생활 블로그

트랙백(0)덧글(0)

Sorting Algorithm efficiency by 북스카이

2011/05/06 07:33
데이터 구조
comsky.egloos.com/4970186
2 comments

데이터 구조 과제로 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가 진리이긴 진리인가보다... 그냥 온 몸에 전율이... ..

-------------------------------<내용 추가 -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 찬양