[알고리즘 ] 알고리즘 분석 (quick sort & quicksort+selection sort)

소개

팀프로젝트로 수행한 알고리즘 분석을 올려놓았습니다.
퀵소트와 퀵소트+셀렉션소트의 time complexity를 비교 분석하였으며 소스코드도 첨부하였습니다. 소스는 유닉스 체제에서 수행하시면 무리없이 수행되리라 생각되어집니다.

목차

1. 알고리즘 설명
2. 수행 결과 제시 및 비교 및 원인분석
3. 이론적 complexity와의 비교 분석
4. threshold값 추정
5. 작은 input size를 갖는 데이터에 대하여 출력한 알고리즘 검증결과
6. 첨부 - 소스코드

본문내용

위에서의 결과에서 보듯이 Selection sort의 subarray값(k값)이 10일 때 가장 빠른 수행시간을 가짐을 알 수 있다. 즉 k=10일 경우 (x-k)log(x-k)>(x-k)log(x-k)+이 식을 만족한다고 할 수 있다. 이와마찬가지로 k=20, k=30일 경우 위식의 값이 역전됨을 짐작할 수 있다.
이것으로 추정할 수 있는 결론은 k의 값이 매우 작으면 작을수록 선택정렬의 사용이 효율적이라는 것이다.

위에서 도표에서 보는 바와 같이 이론치와 실질적인 수행 결과는 조금 다르게 나타난다.
이러한 현상이 나타나는 원인은 우리가 이론치로 Quick sort의 Average case 적용, 난수발생으로 인한 오차 즉, worst-case 와 best-case에 가까운 경우로 걸리는 시간이 역전 된 경우라 생각 할 수 있다.

참고자료

· 없음