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

등록일 2003.05.10 한글 (hwp) | 12페이지 | 가격 6,000원

소개글

팀프로젝트로 수행한 알고리즘 분석을 올려놓았습니다.
퀵소트와 퀵소트+셀렉션소트의 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에 가까운 경우로 걸리는 시간이 역전 된 경우라 생각 할 수 있다.
*원하는 자료를 검색 해 보세요.
  • 버블소트소트의 시간 비교(소팅 순서와 시간비교가 다되어 있습니다) 0페이지
    버블소트소트시간 비교하기 위해 만들어논 프로그램입니다.메뉴로 키 ... 것이고, 소트는 비교를 하면서퀵과 i값이 비교되고 마지막 으로 피봇값과 ... j값이 바뀌는 알고리즘입니다. 실행화면 확인하세요. 다른 자료들과는 틀
  • 소트(Sort) 14페이지
    횟수가 적은 편입니다. 1. 셀렉 소트(Selection Sort) 흔히 ... 소트 알고리즘을 이용하는가에 의해 비교횟수의 차이가 있는데 비교 횟수가 ... 작을 수록 빠른 정렬이 이루어집니다. 일반적으로 소트가 평균 비교
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [알고리즘 ] 알고리즘 분석 (quick sort & quicksort+selection sort)